method running solely on general-purpose computers and the only one faster than ${\cal O}(N\log N)$. In particular, it out-performs the popular tree code by a factor of 10 and more. At $30000{\mathrel{\hbox{\rlap{\hbox{\lower4pt\hbox{$\sim$}}}\hbox{$<$}}}}N{\mathrel{\hbox{\rlap{\hbox{\lower4pt\hbox{$\sim$}}}\hbox{$<$}}}}3\times10^7$, the only technique that requires less CPU time is a combination of the tree code with a [GRAPE-5]{} board [@GRAPE; @G-tree]. Here, the speed-up due to the usage of special-purpose hardware does not quite reach that for direct methods, because of tree-building and other overheads that cannot be done on the [GRAPE]{} board.

Comparison with Fast Multipole Methods {#sec:fmm}
--------------------------------------

Because our code relies on cell-cell interactions, it may be considered a variant of FMM, introduced by Greengard & Rokhlin [@FMMa; @FMMa1]. However, it differs in several ways from most implementations of FMM. (i) the expansions are centered on the cells’ centers of mass instead of the geometrical centers; (ii) a Cartesian Taylor series is used instead of an expansion in spherical harmonics; (iii) the interaction partners are determined by a multipole acceptance criterion rather than by their mutual grid position; (iv) the mutuality of interactions is fully exploited; (v) the expansion order $p$ is fixed and the accuracy controlled by the parameter $\theta$.

[@rrrlrrl]{} & & & 