Scalable Implementations of
Multipole-Accelerated Algorithms for Molecular Dynamics
John A. Board Jr., Ziyad S. Hakura,
William D. Elliott, Daniel C Gray,
William J. Blanke, and James F. Leathrum, Jr.
Abstract
We consider efficient, scalable solutions to the long-range force
computation problem in molecular dynamics (MD) simulation.
Straightforward implementation of a solver for the time-consuming
Coulomb force yields O(N^2) runtime for N atoms in a system; this
quadratic complexity limits the size of systems that can be simulated.
Exclusion of interactions beyond a certain cutoff radius reduces
runtime but also negatively impacts simulation accuracy. By using
algorithms based on the multipole expansion of the potential due to
groups of charged particles, our work permits high-accuracy
simulations which include all pair interactions (i.e. no truncation)
at a runtime cost which grows linearly with the size of the system.
Our algorithms are parallelizable on a range of platforms; we
concentrate on the Kendall Square KSR-1 in this paper. We present
results from four variants of our multipole-accelerated algorithms on
systems of up to a million particles on up to 32 processors.
Back to the Scientific Computions Group Home Page