Barnes-Hut simulation
From Wikipedia, the free encyclopedia
The Barnes-Hut simulation is an algorithm for performing an N-body simulation. It is notable for having order O(n log n) compared to a symplectic integrator which would be O(n2).
The simulation volume is usually divided up into cubic cells via an octree, so that only particles from nearby cells need to be treated individually, and particles in distant cells can be treated as a single large particle centered at its center of mass (or as a low-order multipole expansion). This can dramatically reduce the number of particle pair interactions that must be computed. To prevent the simulation from becoming swamped by computing particle-particle interactions, the cells must be refined to smaller cells in denser parts of the simulation which contain many particles per cell.
[edit] References
- J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324(4), December 1986.
