Barnes–Hut simulation
The Barnes–Hut simulation (Josh Barnes and Piet Hut) 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 (in a 3-dimension space), 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 calculating the force acting on a particle at the point of origin. -
n-Body simulation based on the Barnes-Hut algorithm.
See also
References
- J. Barnes and P. Hut (1986). "A hierarchical O(N log N) force-calculation algorithm". Nature. 324 (4): 446–449. doi:10.1038/324446a0.
{{cite journal}}: Unknown parameter|month=ignored (help) - J. Dubinski (1996). "A Parallel Tree Code". New Astronomy. 1 (2): 133–147. doi:10.1016/S1384-1076(96)00009-7. arXiv:astro-ph/9603097v1.
{{cite journal}}: Unknown parameter|month=ignored (help) - U. Becciani, R. Ansalonib, V. Antonuccio-Delogua, G. Erbaccic, M. Gamberaa, and A. Pagliarod (1997). "A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system". Computer Physics Communications. 106 (1–2): 105–113. doi:10.1016/S0010-4655(97)00102-1.
{{cite journal}}: Unknown parameter|month=ignored (help)CS1 maint: multiple names: authors list (link)