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.
Cited by 546 works. doi:10.1137/0906008
Authors
References
- The Design and Analysis of Computer Algorithms
- Multidimensional binary search trees used for associative searching
- An Algorithm for Finding Best Matches in Logarithmic Expected Time
- The Large-Scale Structure of the Universe
- Computer Simulation Using Particles
- Computer Structures: Principles and Examples
- Numerical treatment of ordinary differential equations by extrapolation methods
- The large-scale structure of the Universe
- Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces
- A Nested Partitioning Procedure for Numerical Multiple Integration