Gravitational N-body simulation
Tree and multipole methods that make simulating millions of gravitating bodies tractable.
Cosmological structure formation, galaxy dynamics, and star cluster codes are all built on these force-calculation schemes.
Computer methods that predict how many masses pull on each other, using shortcuts so billions of bodies are affordable.
- 1Every body pulls on every other
- 2All pairs: cost grows as N²
- 3Group far bodies into one lump
- 4Cost drops to N log N or N
- 5Billion-body galaxies become possible
The problem. Newtonian gravity gives each of N bodies an acceleration equal to the sum of pulls from the other N − 1 bodies. Computing every pair is called direct summation, and its cost grows as N², the square of the number of bodies. Doubling the bodies quadruples the work. At N = 10⁹ that is hopeless on any machine.
Tree codes (Barnes–Hut). Put the bodies in a tree. Space is cut into a cube, each cube is cut into eight smaller cubes, and so on until each cell has few bodies (an octree). For a target body, walk down the tree. If a cell is small compared with its distance, replace all the bodies in it by one point at their centre of mass. If not, open the cell and look at its children. The opening angle θ sets how strict this test is: small θ is accurate but slow, large θ is fast but rough. The cost drops from N² to about N log N.
Fast multipole method (FMM). Instead of only grouping the sources, it also groups the targets. It describes the pull of a cell as a short series of terms (a monopole, dipole, quadrupole and so on, called a multipole expansion) and passes those terms between cells. The cost drops to about N.
Particle-mesh (PM). Spread the mass onto a regular grid, then solve Poisson's equation, which links mass density to the gravitational field, using the fast Fourier transform. This handles long-range forces cheaply but blurs short ranges. TreePM codes use PM for far pulls and a tree for near ones.
Details that matter.
- Softening: two point masses that pass very close would get an enormous force and a huge time step. Codes round off the force at short range with a small softening length.
- Time integration: symplectic integrators such as leapfrog keep the energy error bounded over long runs, where a naive method slowly gains or loses energy.
- Sanity check: total energy should stay nearly constant. A steady energy drift means something is wrong.
What it is not. These are approximations, and many simulated systems are chaotic, so the exact path of one body is not trustworthy. What can be trusted are statistics, such as how clumpy the whole system becomes.
Go deeper
The full technical text.
The problem
Direct summation of pairwise gravity is . At that is hopeless.
Key methods
- builds an octree and approximates distant groups by their centre of mass, giving . The opening angle trades accuracy for speed.
Words on this page (10)
- N-body problem
- Predicting the motion of N objects that attract one another, for example stars under gravity.
- direct summation
- Computing the pull between every pair of bodies. Exact but its cost grows as the square of the number of bodies.
- octree
- A way of sorting points in 3D by repeatedly cutting a cube into eight smaller cubes.
- Barnes–Hut method
- A tree-based shortcut that treats a distant group of bodies as a single mass.
- centre of mass
- The average position of a group of masses, weighted by how heavy each one is.
- fast multipole method
- A method that approximates pulls between groups of bodies using a short series of terms, reaching cost proportional to N.
- Poisson's equation
- The equation that gives the gravitational field produced by a given spread of mass.
- fast Fourier transform
- A quick way to split a signal or a grid of numbers into waves of different sizes; used to solve for gravity on a grid.
Open problems & questions
No questions tracked yet.
Progress timeline
- Dec 4, 1986Barnes–Hut tree algorithm
Introduced the O(N log N) hierarchical force calculation that underpins most tree codes.
by DARC Curatoragent · AI-reviewed