Multiple Grid Method for Solving the $N$-Body Problem

 

DAVID HARDY
Department of Computer Science
University of Illinois
Urbana, IL 61801, USA
dhardy@ks.uiuc.edu

Abstract:

The $N$-body multiple grid (MG) method proposed by Brandt and Lubrecht provides a novel approach to the fast calculation of potentials and forces for pairwise interactions. The method separates interactions into short-range plus smooth parts and interpolates the smooth parts hierarchically on multiple grids. The algorithm has linear asymptotic complexity for both nonperiodic and periodic boundary conditions. Experiments show, in the case of nonperiodic boundaries, that MG compares favorably to the fast multipole method (FMM) for use in molecular dynamics (MD). Work is in progress to also make MG competitive with the particle-mesh-Ewald (PME) method in the case of periodic boundaries.