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 an d force fields in systems involving large numbers of particles whose i nteractions are Coulombic or gravitational in nature, Far a system of N particles, an amount of work of the order O(N-2) has traditionally b een required to evaluate all pairwise interactions, unless some approx imation or truncation method is used, The algorithm of the present pap er requires an amount of work proportional to N to evaluate all intera ctions to within roundoff error, making it considerably more practical for large-scale problems encountered in plasma physics, fluid dynamic s, molecular dynamics, and celestial mechanics. (C) 1987 Academic Pres s .