expected for methods based on cell sinks (implying cell-cell interactions) [@FMMa; @FMMb; @WS], but, to my knowledge, hardly ever shown empirically in three dimensions.

Our code obtains a complexity of less than ${\cal O}(N)$ by employing a mass-dependent tolerance parameter $\theta$. The traditional $\theta=\,$constant results in equal [*relative*]{} errors of each interaction, such that the total error of any body’s force is dominated by the interactions with the most massive cells. By slightly increasing the tolerance parameter for less massive cells, we obtain (approximately) equal [*absolute*]{} errors, resulting in a lower total force error than the traditional method for the same number of interactions. Thus, at the same error, we require less interactions. The additional interactions, arising when increasing $N$, occur at ever less massive cells and hence at ever larger tolerance parameters. This causes the computational costs to rise sub-linear with $N{\mathrel{\hbox{\rlap{\hbox{\lower4pt\hbox{$\sim$}}}\hbox{$>$}}}}10^4$ (depending on the accuracy requirements).

Performance {#sec:per}
-----------

We have shown that on general-purpose computers our code out-performs any competitor code commonly used in the field of stellar dynamics. A recent adaptive 3D implementation of FMM [@FMMb] is also out-performed by a factor of ten ([§\[sec:fmm\]]{}), which is related to the fact that traditional FMM codes appear 