Abstract
Fast methods for calculating two-body interactions have many applications, and for molecular science and cosmology, it is common to employ periodic boundary conditions. However, for the 1/r potential, the energy and forces are ill-defined. Adopted here is the model given by the classic Ewald sum. For the fast calculation of two-body forces, the most celebrated method is the fast multipole method and its tree-code predecessor. However, molecular simulations typically employ mesh-based approximations and the fast Fourier transform. Both types of methods have significant drawbacks, which, in most respects, are overcome by the less well-known multilevel summation method (MSM). Presented here is a realization of the MSM, which can be regarded as a multilevel extension of the (smoothed) particle mesh Ewald (PME) method, but with the Ewald softening replaced by one having a finite range. The two-level (single-grid) version of MSM requires fewer tuning parameters than PME and is marginally faster. Additionally, higher-level versions of MSM scale well to large numbers of processors, whereas PME and other two-level methods do not. Although higher-level versions of MSM are less efficient on a single processor than the two-level version, evidence suggests that they are more efficient than other methods that scale well, such as the fast multipole method and tree codes.