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.
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.
 Jim Demmel's lecture notes contain a tutorial description of the Barnes-Hut algorithm.
 A recent version of the Barnes-Hut algorithm with online documentation.
 The original treecode.
 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