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