# 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

Back to main page.