A fast algorithm for particle simulations (Reprinted from the Journal of Computational Physics, vol 73, pg 325-348, 1987)

An algorithm is presented for the rapid evaluation of the potential and force fields in systems involving large numbers of particles whose interactions are Coulombic or gravitational in nature, Far a system of N particles, an amount of work of the order O(N-2) has traditionally been required to evaluate all pairwise interactions, unless some approximation or truncation method is used, The algorithm of the present paper requires an amount of work proportional to N to evaluate all interactions to within roundoff error, making it considerably more practical for large-scale problems encountered in plasma physics, fluid dynamics, molecular dynamics, and celestial mechanics. (C) 1987 Academic Press .