Fast Adaptive Multiple Algorithm for Particle Simulations. Revision.

摘要

An adaptive algorithm has been constructed for the rapid evaluation of the potentials and force fields due to large scale ensembles of particles of the type encountered in plasma physics, molecular dynamics, fluid dynamics (the vortex method), and celestial mechanics. The algorithm is applicable whenever the fields to be evaluated are Coulombic or gravitational in nature, and yields the potentials to within round-off error. The asymptotic CPU time estimate for the algorithm is of the order O(N), where N is the number of particles in the simulation, and this estimate is independent of the statistics of the charge distribution. Our numerical experiments indicate a tendency of the scheme to be more efficient for non-uniform distributions than for uniform ones. The storage requirements of the algorithm are of the order O(N), do not depend on the statistics of the distribution, and tend to be quite acceptable even for very large numbers of particles. In this paper, a two-dimensional version of the algorithm is described. Generalizing it to the three-dimensional case is fairly straightforward, and will be reported at a later date.