Scalable implementations of multipole-accelerated algorithms for molecular dynamics
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(N2) 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.
