low-accuracy regime, that combines the tree code and FMM whereby taking the better of each. In order to be fully adaptive, we use a hierarchical tree of cubic cells. The force is calculated employing [*mutual*]{} cell-cell interactions, in which both cells are source and sink simultaneously. Whether a given cell-cell interaction can be executed or must be split, is decided using an improved multipole-acceptance criterion (MAC). The new code is a further development of the code presented in [@Da], which in turn may be considered an improvement of a code given in [@WS]. It is substantially faster than the tree code and empirically shows a complexity of ${\cal O}(N)$ or even less.

The paper is organized as follows. In [§\[sec:grav\]]{}, the numerical concepts are presented; [§\[sec:alg\]]{} describes the algorithm; in [§\[sec:assess\]]{} the force errors are empirically assessed for some typical stellar dynamical test cases; [§\[sec:perform\]]{} presents empirical measurements of the complexity and performance, also in comparison to other methods; finally, [§\[sec:summ\]]{} sums up and concludes.

Approximating Gravity {#sec:grav}
=====================

The goal is to approximately compute the gravitational potential $\Phi$ and its derivative, the acceleration, at all body positions ${{\mbox{\boldmath$x$}}}_i$ and generated by all other $N-1$ bodies $$\label{potential}
\Phi({{\mbox{\boldmath$x$}}}_i) =-\sum_{j\neq
  i}\mu_j\,g({{\mbox{\boldmath$x$}}}_i-{{\mbox{\boldmath$x$}}}_j),$$ 