go-v.orgcodex
Menu
Page tools

codex · Astronomy

Barnes–Hut simulation

Diagram for Barnes–Hut simulation
The Barnes–Hut simulation (named after Joshua Barnes and Piet Hut) is an approximation 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). · image: Wikimedia Commons

The Barnes–Hut simulation (named after Joshua Barnes and Piet Hut) is an approximation 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 three-dimensional 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 the cell's center of mass (or as a low-order multipole expansion). This can dramatically reduce the number of particle pair interactions that must be computed.

Some of the most demanding high-performance computing projects perform computational astrophysics using the Barnes–Hut treecode algorithm, such as DEGIMA.

Wikipedia contributors, "Barnes–Hut simulation", Wikipedia, revision 1380815355, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Astronomy · Search the codex