Particle Mesh Ewald (PME) has become a standard method for treating long-range electrostatics in molecular simulations. Although the method has inferior asymptotic computational complexity to its linear scaling competitors, it remains enormously popular due to its high efficiency, which stems from the use of fast Fourier transforms (FFTs). This use of FFTs provides great challenges for scaling the method up to massively parallel systems, in large part because of the need to transfer large amounts of data. In this work, we demonstrate that this data transfer volume can be greatly reduced as a natural consequence of the structure of the PME equations. We also suggest an alternative algorithm that supplants the FFT with a linear algebra approach, which further decreases communication costs at the expense of increased asymptotic computational complexity. This linear algebra based approach is demonstrated to have great potential for latency hiding by interleaving communication and computation steps of the short- and long-range electrostatic terms.