Book Description
The evaluation of Coulombic or gravitational interactions in large ensembles of particles is an integral part of the numerical simulation of a large number of physical processes. Examples include celestial mechanics, plasma physics, the vortex method in fluid dynamics, molecular dynamics, molecular dynamics, and the solution of the Laplace equation via potential theory. A numerical model follows the trajectories of a number of particles moving in accordance with Newton's second law of motion in a field generated by the whole ensemble. In many situations, in order to be of physical interest, the simulation has to involve thousands of particles (or more), and the fields have to be evaluated for a large number of configurations. Unfortunately, an amount of work of the order O N-sg has traditionally been required to evaluate all pairwise interactions in a system of N particles, unless some approximation or truncation method is used. Large scale simulations have been extremely expensive in some cases, and prohibitive in others. An algorithm is presented for the rapid evaluation of the potential and force fields in large scale systems of particles. To evaluate all pairwise Coulombic interactions of N particles to within round off error, the algorithm requires an amount of work proportional to N, and this estimate does not depend on the statistics of the distribution. Both two and three dimensional versions of the algorithm have been constructed. Applications to several problems in physics, chemistry, biology, and numerical complex analysis are discussed.
