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 direct-sum algorithm 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.
 Particle distribution resembling two neighboring galaxies. |
 Complete barnes hut tree. (Nodes that do not contain particles are not drawn) |
 Nodes of the barnes hut tree used for calculation the force acting on a particle at the point of origin. |
 N-Body simulation based on a Barnes-Hut-Algorithm. |
References
- J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324(4), December 1986.
- A Parallel Tree Code, J. Dubinski, arXiv:astro-ph/9603097v1.
- A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system, U. Becciani, R. Ansalonib, V. Antonuccio-Delogua, G. Erbaccic, M. Gamberaa, and A. Pagliarod, Computer Physics Communications, Volume 106, Issues 1-2, 2 October 1997, Pages 105-113.
Software : Numerical Codes
See also
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
