Barnes–Hut simulation

Builds on N-body simulation Tree Newton's law of universal gravitation

Definition

Let particles with masses $m_1, \dots, m_N > 0$ and positions $x_1, \dots, x_N \in \R^3$ be given, and fix an opening angle $\theta > 0$ . The Barnes–Hut algorithm computes approximate gravitational accelerations as follows.

Build an octree. The root is a cube containing all particles. A cube with more than one particle is split into eight equal subcubes, recursively, until each leaf holds at most one particle.
For each cell $C$ of the tree, store its total mass $M_C$ and its centre of mass $X_C$ .
To compute the acceleration of particle $i$ , traverse the tree from the root. Let a cell $C$ have side $s_C$ and distance $d = \norm{x_i - X_C}$ . If $s_C / d < \theta$ or $C$ is a leaf, add the term $-G M_C (x_i - X_C)/d^3$ , omitting particle $i$ itself. Otherwise visit the children of $C$ .

A Barnes–Hut simulation is an N-body simulation whose accelerations at each time step are computed by this algorithm.

Remarks

Example: with $\theta \to 0$ , every cell is opened down to the leaves, and the method returns the exact sum of Newton's law of gravitation over all pairs. With a typical value $\theta \approx 0.5$ to $1$ , the number of cells visited per particle grows like $\log N$ for roughly uniform distributions, so the cost per step is of order $N \log N$ .

Non-example: replacing every cell, near or far, by its centre of mass (no opening criterion) is not the Barnes–Hut algorithm; it gives large errors for nearby particles.

The approximation by the centre of mass is the monopole term of a multipole expansion; variants add the quadrupole term for better accuracy.

Reading path

To understand this page from the ground up, read these 46 pages in order. The foundations come first.

Derivative concept
Differential equation concept
Euclidean space object
Euclidean vector concept
Function concept
Interval concept
N-body simulation concept
Ordinary differential equation concept
Tree concept
Velocity concept
Fréchet derivative definition
Ordinary differential equation definition
Cross product definition
Function of several variables concept
Vector-valued function concept
Lipschitz condition definition
Classical mechanics concept
Limit of a function of several variables concept
Momentum concept
Solution of an ordinary differential equation definition
Partial derivative concept
Inertial frame of reference concept
Continuity in R^n definition
Differentiable function of several variables definition
Initial value problem definition
Partial derivative definition
Newton's laws of motion statement
Differentiable on an open set definition
Gradient definition
Higher partial derivatives definition
Picard–Lindelöf hypotheses definition
Iterated derivative definition
Picard operator definition
C^k function characterised by continuous derivatives statement
Integral equation form of an initial value problem statement
An iterate of the Picard operator is a contraction statement
Vector field definition
Picard–Lindelöf theorem statement
Conservative vector field definition
Classical mechanics definition
Momentum definition
Potential energy definition
Angular momentum definition
Central force definition
Newton's law of universal gravitation statement
Barnes–Hut simulation definition

Tag	`S60M061DZZ`
URI	`m2://S60M061DZZ`
Kind	definition
Writing	W0 stub
MSC	85-08, 70F10, 65Z05
Defines	Barnes–Hut simulation
Uses	N-body simulation, Tree, Newton's law of universal gravitation
Changed	3 November 2026

Barnes–Hut simulation

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here