next up previous contents index
Next: 12.4.2 Computing Forces Up: 12.4 Tree Codes for Previous: 12.4 Tree Codes for

12.4.1 Oct-Trees


There are a number of ways to utilize this fact in a computer simulation [Appel:85a], [Barnes:86a], [Greengard:87b], [Zhao:87a]. The methods differ in choice of data structure, level of mathematical rigor, and complexity of the fundamental interactions. We shall consider an adaptive tree data structure, and an algorithm that treats each body independently. The algorithm begins by partitioning space into an oct-tree, that is, a tree whose nodes correspond to cubical regions of space. Each node may have up to eight daughter nodes, corresponding to the eight subcubes that are obtained by dividing in half in each Cartesian  direction. The tree is defined by the following properties:

  1. All terminal nodes of the tree have either one or zero bodies.
  2. All nodes with one or zero bodies are terminal.
Oct-trees are somewhat difficult to draw on two-dimensional paper. The corresponding analog in two dimensions is a quad-tree. Figure 12.10a shows a very shallow quad-tree, with each of the square cells explicitly represented. Figure 12.10b shows the same tree in a more compact, ``flattened'' representation. The ``flattened'' representation has a tendency to de-emphasize the importance of the higher levels of the tree. This is purely an artifact of the graphical representation. In all cases, the tree consists of both terminal nodes and internal nodes. Figure 12.11 shows a quad-tree derived from 10,000 bodies distributed at random on a disc.

Figure 12.10: (a) Expanded and (b) Flat Representation of an Adaptive Tree

Figure 12.11: 10,000 Body Barnes-Hut Tree

The oct-tree  provides a convenient data structure which allows us to record the properties of the matter distribution on all length scales. It is especially convenient for astrophysical systems because it is adaptive. That is, the depth of the tree adjusts itself automatically to the local particle density. In order to use an approximation like Equation 12.5, we need to know certain properties of the matter distribution in each cell. In the simplest case, these properties are the mass and center-of-mass of the matter distribution, but it is possible to use quadrupole moments [Hernquist:87a], or higher-order moments [Salmon:90a] for added accuracy. All of these properties may be computed by a bottom-up traversal of the tree, combining the properties of the ``daughters'' of a node to get the properties of the node itself. The time required for this bottom-up traversal is proportional to the number of internal nodes in the tree, that is, .

next up previous contents index
Next: 12.4.2 Computing Forces Up: 12.4 Tree Codes for Previous: 12.4 Tree Codes for

Guy Robinson
Wed Mar 1 10:19:35 EST 1995