Scalable Variants of Multipole-Accelerated Algorithms for Molecular Dynamics Applications

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. 1 Multipole-accelerated algorithms In molecular dynamics simulation (MD), the N-body problem manifests itself as the need to compute the long-range electrostatic forces acting between all the charged atoms in a molecular syst..