---
author:
- Walter Dehnen
title: 'A Hierarchical ${\cal O}(N)$ Force Calculation Algorithm'
---

Introduction {#sec:intro}
============

In $N$-body simulations of stellar dynamics (or any other dynamics incorporating long-range forces), the computation, at every time step, of the gravitational forces between $N$ mutually interacting bodies dominates the operational effort. In many situations, such as studies of collisionless stellar systems, the error of these simulations is dominated by the noise in the distribution of the bodies, whose number $N$ is just a numerical parameter. Therefore, instead of computing the forces exactly by direct summation over all pairs of bodies, one may use approximate but much faster methods, allowing substantially larger $N$ and hence significantly reduced noise.

In stellar dynamics, one of the most commonly used approximate methods is the Barnes & Hut tree code [@BH] and its clones. With these methods, one first sorts the bodies into a hierarchical tree of cubic cells and pre-computes multipole moments of each cell. Next, the force at any body’s position and generated by the contents of some cell is calculated by a multipole expansion if the cell is well-separated from the body; otherwise the forces generated by the cell’s child nodes are taken. This 