The Barnes-Hut algorithm is a classic solution method for the
N-body problem [6]. An N-body problem is often characterized by
the necessity to interact each of the N bodies with every other one
[3, 7], potentially an *O(n^2)* set of operations. A trivial
algorithm is necessarily limited by the number of objects that it can
interact per unit time. It may additionally incur memory limitations
and an unbalanced ratio of computation to communication due to latency
effects, bandwidth constraints, or network overhead. Barnes-Hut
attempts to avoid these pitfalls by partitioning the data set into
space-separated clusters and using this information to prune the
number of interactions from *O(n^2)* to approximately *O(n
log n)*. (For an in-depth discussion on the time and error bounds,
please see [13]. We include a summary.)
It does so by taking advantage of the *locality* inherent
in the space-partitioning: groups of particles far from one another
can approximate their effect on each other, rather than calculate it
precisely.

There are four basic steps performed during each iteration of the algorithm. They include:

- a
*tree-build*phase where a space-separated decomposition of the bodies and the resulting tree is created - a
*load-balancing*phase where the timestep's necessary total work (or an approximation thereof) is partitioned among the processors - a
*particle interaction*(or*force computation*) phase where some body-to-body interaction rule (such as he inverse-square law for gravity) is used to calculate the effects of each particle on the others - an
*update*phase where the effects of the interactions are propagated in preparation for the next iteration

(Note that in some implementations, the tree-build and load-balancing stages are done in tandem.)

In short, once the bodies have been partitioned into spatially
decomposed subsets by the tree-build phase, these subsets' local
dependencies should far outweigh those of more distant clusters of nodes.
Thus, they may act as a group, or *cell*, when affecting
these non-local bodies. The adaptive nature of the tree
insures that there is sufficient precision in the separations to
enable this simplification.

During the *force computation*
phase, body-to-body and body-to-cell interactions are actually performed.
The hope is that by choosing the groupings successfully in the tree-build
phase, the number of force calculations in this third phase can be
drastically reduced. In all current implementations of Barnes-Hut, the
time required for the force-calculation phase dominates the time required
to build the space-partitioning tree [3, 4, 8, 10]. Nevertheless, the
computation phase in inherently dependent on the tree-build in that
the part ions must successfully expose where simplification is reasonable.

There are many factors that contribute to difficulty of the problem:

- The body distribution is:
- highly non-uniform
- dynamic

- The computation requires adaptive data structures
- Updates need both local and global data
- often very large data sets are involved (sometimes as large as possible.)

Continue to Motivation

See a time step view of evolving galaxies

maintained by <hodes@cs.berkeley.edu>