Multipole-Based Algorithms for Efficient Calculation of Forces and Potentials in Macroscopic Periodic Assemblies of Particles

A new and efficient algorithm based on multipole techniques is presented which calculates the electrostatic forces and potentials in macroscopic periodic assemblies of particles. The Fast Multipole Algorithm (FMA) can be used to compute forces within the n-particle unit cell in O(n) time. For the cubic lattice, forces due to a 3^k &times 3^k &times 3^k lattice of images of the unit cell can be computed in O(nk² + k³ log k) time to arbitrary precision. For biological systems, k need only be a small constant, giving an algorithm linear in n. The algorithm was easily added onto an existing FMA implementation, and computational results are presented. Accurate electrostatic computations were done on a 3^8 × 3^8 × 3^8 region of unit cells at only a twofold cost over computing the forces and potentials within the 100000 particle unit cell alone