# The Barnes-Hut Hierarchical Force-calculation Algorithm

The
Barnes-Hut hierarchical force-calculation algorithm exploits the fact
that, at a distance, the combined potential of a group of particles can
be approximated by the potential of the center of mass of that group.
As illustrated to the right, the algorithm makes use of a hierarchical
quad-tree (or oct-tree in 3D)
decomposition of the space containing the particles, and associates with
each region its center of mass.
After the tree (to the left) is built, the force calculation
traverses the tree top down for each particle to accumulate the total
force on the particle. Subregions are explored only if the region's
center of mass is not sufficiently far away from the particle to be
used as an approximation.
Here is a pseudo-code for this algorithm:

function *treeForce* (*p*, *node*) =
if region at *node* contains 1 particle then
compute direct interaction between the two particles
else
if *p* is distant enough from region at *node* then
compute direct interaction between *p*
and the center-of-mass of *node*
else
for each *subnode* of *node* in parallel
compute *treeForce* (*p*, *subnode*) recursively
end for each
return the sum of the results
end if
end if

References [1-3] provide details about the criteria to
be used to decide when to traverse the children of a node, about the
approximations used to represent a region, and about the force
computations.

The *treeForce*

computation for each particle is
independent and can be computed in parallel. Moreover, the recursive
force-computations in the tree traversal are independent and can be
computed in parallel. The parallelism specified in
*treeForce*

is dynamic since the available parallelism
increases with the depth of the recursion. It is irregular because the
degree of parallelism specified and the locality of the interactions
depends on the distribution of the particles.

This problem is suggested for consideration in Dagstuhl because the
algorithm can be succinctly expressed in a high-level notation, yet an
efficient implementation is challenging. Furthermore, some comparative
performance data is available for low-level implementations.

## Online references

[1] Jim
Demmel's lecture notes contain a tutorial description of the
Barnes-Hut algorithm.

[2] A
recent version of the Barnes-Hut algorithm with online
documentation.

[3] The
original treecode.

[4] A survey of
n-body methods with pointers to the literature and to the Web by Amara
Graps.

Back to main page.

Last modified: Wed Feb 3 16:40:40 JST 1999