Scalable Variants of Multipole-Accelerated Algorithms
for Molecular Dynamics Applications
John A. Board, Jr., Ziyad S. Hakura,
William D. Elliott and
William T. Rankin
Abstract
Multipole-based algorithms allow for reduction in the effort required
to solve the N-body problem of
electrostatics or graviation from
O(N^2) to O(N log N) or even O(N) in the
number of interacting bodies N.
We consider serial and parallel implementations of variants of the algorithms of
Barnes and Hut, and
of Greengard and Rokhlin, as well as a hybrid algorithm. Coupled with
other optimizations such as a Fourier-domain computation of
multipole series translations, we find the hybrid algorithm to be most efficient
over a wide range of accuracy and system sizes relevant to molecular
dynamics. The algorithms have been demonstrated to scale
to 64 processors, and we expect them to be valid out to at least 512
processors on large (1 million particle) problems.
Back to the Scientific Computions Group Home Page