Multipole-Based Algorithms for Efficient Calculation of Forces and
Potentials in Macroscopic Periodic Assemblies of Particles
Christophe G. Lambert
Abstract
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 3x3x3
lattice of images of the unit cell can be computed in
O( n k^2 + k^3 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 x 3^8 x 3^8
region of unit cells at only a twofold cost over
computing the forces and potentials within the 100000 particle unit
cell alone.
Back to the Scientific Computions Group Home Page