Barnes–Hut simulation
   HOME

TheInfoList



OR:

The Barnes–Hut simulation (named after Josh Barnes and
Piet Hut Piet Hut (born September 26, 1952) is a Dutch-American astrophysicist, who divides his time between research in computer simulations of dense stellar systems and broadly interdisciplinary collaborations, ranging from other fields in natural scien ...
) is an
approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
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(''n''2). The simulation volume is usually divided up into cubic cells via an
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 ana ...
(in a three-dimensional space), so that only
particles In the physical sciences, a particle (or corpuscule in older texts) is a small localized object which can be described by several physical or chemical properties, such as volume, density, or mass. They vary greatly in size or quantity, from s ...
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 In physics, the center of mass of a distribution of mass in space (sometimes referred to as the balance point) is the unique point where the weighted relative position of the distributed mass sums to zero. This is the point to which a force may ...
(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 High-performance computing (HPC) uses supercomputers and computer clusters to solve advanced computation problems. Overview HPC integrates systems administration (including network and security knowledge) and parallel programming into a mult ...
projects do
computational astrophysics Computational astrophysics refers to the methods and computing tools developed and used in astrophysics research. Like computational chemistry or computational physics, it is both a specific branch of theoretical astrophysics and an interdiscipli ...
using the Barnes–Hut treecode algorithm, such as DEGIMA.


Algorithm


The Barnes–Hut tree

In a three-dimensional ''n''-body simulation, the Barnes–Hut algorithm
recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
divides the ''n'' bodies into groups by storing them in an
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 ana ...
(or a
quad-tree A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four ...
in a 2D simulation). Each
node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...
in this tree represents a region of the three-dimensional space. The topmost node represents the whole space, and its eight children represent the eight octants of the space. The space is recursively subdivided into octants until each subdivision contains 0 or 1 bodies (some regions do not have bodies in all of their octants). There are two types of nodes in the octree: internal and external nodes. An external node has no children and is either empty or represents a single body. Each internal node represents the group of bodies beneath it, and stores the
center of mass In physics, the center of mass of a distribution of mass in space (sometimes referred to as the balance point) is the unique point where the weighted relative position of the distributed mass sums to zero. This is the point to which a force may ...
and the total mass of all its children bodies. Image:Barnes_hut_partikel.png, Particle distribution resembling two neighboring galaxies. Image:Barnes_hut_tree.png, Complete Barnes–Hut tree. (Nodes that do not contain particles are not drawn) Image:Barnes_hut_used_nodes.png, Nodes of the Barnes–Hut tree used for calculating the force acting on a particle at the point of origin. File:Galaxy collision.ogv , ''n''-Body simulation based on the Barnes–Hut algorithm.


Calculating the force acting on a body

To calculate the
net force Net Force may refer to: * Net force, the overall force acting on an object * ''NetForce'' (film), a 1999 American television film * Tom Clancy's Net Force, a novel series * Tom Clancy's Net Force Explorers Tom Clancy's Net Force Explorers or Ne ...
on a particular body, the nodes of the tree are traversed, starting from the root. If the center of mass of an internal node is sufficiently far from the body, the bodies contained in that part of the tree are treated as a single particle whose position and mass is respectively the center of mass and total mass of the internal node. If the internal node is sufficiently close to the body, the process is repeated for each of its children. Whether a node is or isn't sufficiently far away from a body, depends on the quotient s/d, where ''s'' is the width of the region represented by the internal node, and ''d'' is the distance between the body and the node's center of mass. The node is sufficiently far away when this ratio is smaller than a threshold value ''θ''. The parameter ''θ'' determines the accuracy of the simulation; larger values of ''θ'' increase the speed of the simulation but decreases its accuracy. If ''θ'' = 0, no internal node is treated as a single body and the algorithm degenerates to a direct-sum algorithm.


See also

*
NEMO (Stellar Dynamics Toolbox) NEMO (Not Everybody Must Observe) is a toolkit for stellar dynamics. At its core it manipulates an ''n''-body system (snapshot), but can also derive or compute orbits, derive images and extract tables to take to other analysis systems. Architec ...
*
Nearest neighbor search Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...
*
Fast multipole method __NOTOC__ The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the ''n''-body problem. It does this by expanding the system Green's function using a multipole expansion, w ...


References and sources

;References ;Sources * * * *


External links


Treecodes, J. BarnesHTML5/JavaScript Example Graphical Barnes–Hut SimulationPEPC – The Pretty Efficient Parallel Coulomb solver
an open-source parallel Barnes–Hut tree code with exchangeable interaction kernel for a multitude of applications
Parallel GPU N-body simulation program with fast stackless particles tree traversalBarnes-Hut galaxy simulator
at beltoforion.de {{DEFAULTSORT:Barnes-Hut simulation Simulation Gravity Physical cosmology Numerical integration (quadrature) Articles containing video clips