A comparison of algorithms for long-range interactions

Abstract The long-range gravitational and Coulombic 1 r potential plays an important role in astrophysical and molecular simulations. In astrophysics, the potential models the interactions of individual stars or complete galaxies. In molecular simulations, it is used to model charged ionic particles. As opposed to the short-range van der Waals interactions, which decay to zero very rapidly with increasing distance, long-range interactions cannot simply be truncated, as this may result in unphysical behavior at the cut-off distance. The long-range interaction is usually handled by special algorithms, in order to decrease the intrinsically large CPU demand. We study and compare several algorithms for the treatment of the long-range 1 r potential. Under consideration are the linear algorithms of Appel and Greengard, as well as a combination of these two algorithms. We show that the algorithms are computationally akin, and that their combination yields an adaptive version of Greengard's algorithm. The standard O(N 3 2 ) algorithm using Ewald's summation for the treatment of periodic systems is also described, and compared with Greengard's algorithm. Our main interests are computational complexity, accuracy and CPU demand.