technique reduces the number of interactions per body to ${\cal O}(\log N)$ and hence results in an overall complexity of ${\cal O}(N\log N)$.

Another technique used frequently, for instance in molecular dynamics, is Greengard & Rokhlin’s [@FMMa; @FMMa1] fast multipole method (FMM) and its variants. Traditionally, these methods first sort the bodies into a hierarchy of nested grids, pre-compute multipole moments of each cell, and then compute the forces between grid cells by a multipole expansion, usually in spherical harmonics. That is, cells are not only sources but also sinks, which formally reduces the complexity to ${\cal O}(N)$, although the author is not aware of an empirical demonstration in three dimensions[^1].

Currently, no useful implementation of FMM for application in stellar dynamics exists. In fact, it has been shown [@CM] that, for this purpose, the FMM in its traditional form cannot compete with the tree code. The reason, presumably, is two-fold: first, because stellar systems are very inhomogeneous, non-adaptive methods are less useful; second FMM codes are traditionally designed for high accuracy, whereas in collisionless stellar dynamics a relative force error of few $10^{-3}$ is often sufficient.

Here, we describe in detail a new code, designed for application in the 