An O(N log N) integration scheme for collisional stellar systems

This is the authors' abstract. We don't add key points for this paper.

A novel tree-based, high-order integration scheme for the numerical simulation of collisional N-body systems is presented. In the present implementation the tree is allowed to deform with time, and the properties of each component cell are not calculated afresh at each step but instead are predicted only as needed. Cells are represented by a multipole expansion that can extend as far as the octupole term, depending on the relative costs of the multipole and individual-particle calculations. A block time step algorithm is used to simplify scheduling and to allow full vectorization of the code. The integrator conserves energy to a few parts per million per crossing time, and its measured O(N exp 1.5) scaling suggests that it will become competitive with NBODY5, the 'standard' high-precision integrator for small systems, for N greater than about 10,000. It is concluded that tree-based schemes can be confidently applied to collisional problems without excessive concern that the tree algorithm will seriously disturb the relaxation processes that drive the evolution.