Barnes–Hut simulation

The Barnes-Hut algorithm is a 1986 posted by Josh Barnes and Piet Hut approximation method that allows an effective computation of the forces in an N- body problem. In contrast to the direct summation of the forces whose computational complexity increases with reduced effort on the Barnes-Hut algorithm.

Motivation

The simulation of N- body problems is a standard task of astronomy. In such a problem, a number (N) of objects move under the influence of a force, which in turn depends on the positions of all the other body. As an example, we refer the motion of stars in the gravitational field of a galaxy. The direct integration is very complicated as the number of bodies, as the force acting on a body is the sum of all forces acting on the other bodies on it. Calculations based on the direct summation forces are therefore with increasing body number (N > 10000) quickly ineffectual, since the total number of force calculations:

This trend can be minimized by using hochparallelisierter computer hardware (GPU) to counteract, however, the problem shifts so only to larger particle numbers. For effective simulations with millions or even billions of particles are necessary algorithms whose computational effort does not increase quadratically with the number of particles. One of these algorithms is that of Barnes and Hut.

Operation

The Barnes-Hut algorithm reduces the number of forces to be calculated by appropriately combining of particle groups to pseudo. The basic idea is that the force exerted by a group of particles on a single particle force can be approximated to a good approximation by the action of a single mass in the center of mass of the particle group. So you can, for example, the force exerted by the Andromeda galaxy to the sun, very good approach by a point mass, which is located in the center of the Andromeda galaxy and its mass has. This approximation is only permitted if the distance of the group from individual particles is large and the group diameter in proportion to the distance small. The ratio of diameter group to group distance is called multipole acceptance criterion (English: MAC; Multipole Acceptance Criterion) referred to:

The smaller, the better the approximation. Exceeds a certain threshold value, the approximation should not be used to avoid major mistakes. The algorithm uses this principle to by recursively partitioning the area into quadrants simulation (2D ) or octants (3D). The particles are stored in the node of the resulting tree. If the distance of a node from a single particle is large enough, the power calculation is not directly between the particles, but between the individual particles and the center of mass of the node.