Parallel multigrid summation for the N-body problem

An Θ(n) parallel multigrid summation method (MG) for the N-body problem is presented. The method was originally devised for vacuum boundary conditions. Here, it is extended to periodic boundary conditions and implemented in parallel using force decomposition and MPI. MG is based on a hierarchical decomposition of computational kernels on multiple grids. For low accuracy calculations, appropriate for molecular dynamics, a sequential implementation is as fast or faster than particle mesh Ewald (PME). Our parallel implementation is more scalable than PME. The method can be combined with multiple time stepping integrators to produce a powerful simulation protocol for simulation of biological molecules and other materials. The parallel implementation is tested on both a Linux cluster with Myrinet interconnect and a shared memory computer. It is available as open-source at http://protomol.sourceforge.net. An auxiliary tool allows the automatic selection of optimal parameters for MG, and is available at http://mdsimaid.cse.nd.edu.