A Multipole-Based Algorithm for Efficient Calculation of Forces and Potentials in Macroscopic Periodic Assemblies of Particles.

C. G. Lambert and J. A. Board, Jr.

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 3^k X 3^k X 3^k lattice of images of the unit cell, containing 3^(3k) n particles, can be computed in O(n k^2 + k^3 log(k)) time to arbitrary precision.

The algorithm was readily 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 100000-particle unit cells, giving a volume of 28 quadrillion particles at less than a twofold cost over computing the forces and potentials in the unit cell alone. In practice, a k=4..6 simulation approximates the true infinite lattice Ewald sum forces (including the shape-dependant dipole correction) to high accuracy,

The method extends to non-cubic unit cell shapes, and non-cubic macroscopic shapes, making it possible, for instance, to efficiently simulate a membrane unit cell periodically replicated in two dimensions. The forces can be computed even when the unit cell is not charge neutral, as is often the case for biological and other ionic systems.

Key Words: Ewald sum, Fast Multipole Algorithm, Particles, Algorithms, Periodic Boundary Conditions, Potential Theory, Molecular Dynamics


Back to the Scientific Computions Group Home Page


This page last modified 7/13/95 by Daniel Paul