Barnes-Hut Algorithm

The Barnes-Hut algorithm is an approximation method published in 1986 by Josh Barnes and Piet Hut , which enables an effective calculation of the forces in an N-body problem . In contrast to the direct summation of the forces, the computational effort of which increases with it , the effort with the Barnes-Hut algorithm is reduced to . ${\ displaystyle O (N ^ {2})}$ ${\ displaystyle O (N \ log N)}$

motivation

The simulation of N-body problems is a standard task in astronomy. In such a problem, a number (N) of bodies move under the influence of a force which in turn depends on the positions of all other bodies. An example is the movement of stars in the gravitational field of a galaxy. The direct integration is very complex with an increasing number of bodies, since the force acting on one body is the sum of all forces that act on it from the other bodies. Calculations based on the direct summation of forces therefore quickly become ineffective as the number of bodies increases (N> 10000), because the total number of force calculations is:

{\ displaystyle {\ frac {1} {2}} N (N-1) \ approx O (N ^ {2})}

This trend can be counteracted by using highly parallelized computer hardware ( GPU ), but the problem only shifts towards larger numbers of particles. For effective simulations with several million or even billions of particles, algorithms are required whose computational effort does not increase quadratically with the number of particles. One of these algorithms is that of Barnes and Hut.

Particle distribution that is modeled on two neighboring galaxies.

Whole Barnes Hat Tree. The area is recursively subdivided until each particle is in its own cell.

The cells of the Barnes-Hut tree, which are used to calculate the force on a particle in the coordinate origin.

Play media file

The calculations for interacting galaxies is a typical use case for Barnes-Hut simulations.

Graph drawing

The pairwise calculation of forces between a large number of objects is also a problem within force-based graph drawing as part of computer science . The edges between the nodes of a graph are interpreted as a system of springs and the graph should be drawn in the plane in such a way that the spring forces cancel each other out. The Barnes-Hut algorithm enables the forces to be calculated iteratively and the nodes to be repositioned.

functionality

The Barnes-Hut algorithm reduces the number of forces to be calculated by appropriately combining groups of particles into pseudoparticles. The basic idea is that the force exerted by a particle group on a single particle can be approximated to a very good approximation by the effect of a single mass in the center of mass of the particle group. For example, the force exerted by the Andromeda galaxy on the sun can be very well approximated by a point mass that is located in the center of the Andromeda galaxy and that has its mass. However, this approximation is only permissible if the distance between the group and the individual particle is large and the group diameter is small in relation to the distance. The ratio of group diameter to group distance is referred to as the Multipole Acceptance Criterion (MAC; Multipole Acceptance Criterion): ${\ displaystyle r}$ ${\ displaystyle d}$

{\ displaystyle \ theta = {\ frac {d} {r}}}

The smaller , the better the approximation. If a certain threshold value is exceeded , the approximation should no longer be used in order to avoid larger errors. The algorithm implements this principle by recursively dividing the simulation area into quadrants (2D) or octants (3D). The particles are saved in the nodes of the resulting tree structure. If the distance between a node and an individual particle is large enough, the force calculation is no longer carried out directly between the particles, but between the individual particle and the center of mass of the node. ${\ displaystyle \ theta}$ ${\ displaystyle \ theta}$

The force exerted by a particle distribution on an individual particle can be approximated by the force emanating from a point mass if the distance between the particle group and the individual particle is large in relation to the group size.

The gravitational effect of the star cluster and star B on star A can be approximated as a point mass due to the great distance. But even within the star cluster, the gravitational force of the star cluster on star B can be approximated by a point mass, since star B is far enough away from the star cluster.

Web links

German

Detailed description of the implementation of the Barnes-Hut algorithm

English

J. Barnes and P. Hut: A hierarchical O (N log N) force-calculation algorithm in Nature , 324 (4), December 1986
Fast Hierarchical Methods for the N-body Problem, Part 1, CS267 , Lecture 24, April 11, 1996
Video of a particle simulation with 8.7 million particles using the Barnes-Hut algorithm calculated on multiple GPUs (youtube.com)
PEPC - The Pretty Efficient Parallel Coulomb Solver , a parallel open-source implementation of the Barnes-Hut algorithm with exchangeable interaction kernel for versatile applications

swell

^ Yifan Hu (2006) Efficient, High-Quality Force-Directed Graph Drawing In The Mathematica Journal

[1] Yifan Hu (2006) Efficient, High-Quality Force-Directed Graph Drawing In The Mathematica Journal