An Efficient Program for Many-Body Simulation
Andrew W. Appel · SIAM Journal on Scientific and Statistical Computing · 1985
The simulation of N particles interacting in a gravitational force field is useful in astrophysics, but such simulations become costly for large N. Representing the universe as a tree structure with the particles at the leaves and internal nodes labeled with the centers of mass of their descendants allows several simultaneous attacks on the computation time required by the problem. These approaches range from algorithmic changes (replacing an $O(N^2 )$ algorithm with an algorithm whose time-complexity is believed to be $O(N\log N)$) to data structure modifications, code-tuning, and hardware modifications. The changes reduced the running time of a large problem $(N = 10,000)$ by a factor of four hundred. This paper describes both the particular program and the methodology underlying such speedups.