Barnes-Hut simulation
Encyclopedia
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.
Piet Hut
Piet Hut is a Dutch astrophysicist who has made his career in the United States. Hut is Professor of Interdisciplinary Studies at the Institute for Advanced Study in Princeton. He was born in Utrecht in The Netherlands....
) is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for performing an n-body simulation
N-body simulation
An N-body simulation is a simulation of a dynamical system of particles, usually under the influence of physical forces, such as gravity . In cosmology, they are used to study processes of non-linear structure formation such as the process of forming galaxy filaments and galaxy halos from dark...
. It is notable for having order
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
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
Octree
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
(in a 3-dimension space), so that only particles
Point particle
A point particle is an idealization of particles heavily used in physics. Its defining feature is that it lacks spatial extension: being zero-dimensional, it does not take up space...
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
Center of mass
In physics, the center of mass or barycenter of a system is the average location of all of its mass. In the case of a rigid body, the position of the center of mass is fixed in relation to the body...
(or as a low-order multipole expansion
Multipole expansion
A multipole expansion is a mathematical series representing a function that depends on angles — usually the two angles on a sphere. These series are useful because they can often be truncated, meaning that only the first few terms need to be retained for a good approximation to the original...
). 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.