The Barnes-Hut (1986) algorithm works by grouping particles using a hierarchy of cubes arranged in oct-tree structure i.e. each node in the tree has 8 siblings. The system is first surrounded by a single cube or cell encompassing all of the particles. This main cell is subdivided into 8 subcells, each containing their own subset of the particles. The tree structure continues down in scale until cells contain only 1 particle. For each cell or node in the tree, we calculate the total mass, center of mass and higher order multipole moments (typically only up to quadrupole order). This tree structure can be built very rapidly making it feasible to rebuild it at each time step. The tree can be constructed bottom-up i.e. by inserting one particle at a time (Barnes & Hut 1986) or top-down by sorting particles across divisions. Both methods take time and in practice only a few percent of total time per step.

The force on a particle in the system can be evaluated by ``walking'' down the tree level by level beginning with the top cell. At each level, a cell is added to an interaction list if the cell is distant enough for a force evaluation. If the cell is too close, it is ``opened'' and the 8 subcells are either used for the force evaluation or opened further. The walk ends when all cells which pass the opening test and any single particles are acquired. The accumulated list of interacting cells and particles is then looped through to calculate the force on the given particle and this amounts to the bulk of the computation. In this way, the number of interactions computed is significantly smaller than a direct N-body method with the number scaling as (Barnes & Hut 1986). Typically, there are interactions per particle on average in a simulation with particles making the algorithm significantly faster than a direct summation method.

Wed May 1 11:12:33 PDT 1996