A fast multipole method for stellar dynamics
The approximate computation of all gravitational forces between N interacting particles via the fast multipole method (FMM) can be made as accurate as direct summation, but requires less than O ( N ) operations. FMM groups particles into spatially bounded cells and uses cell-cell interactions to approximate the force at any position within the sink cell by a Taylor expansion obtained from the multipole expansion of the source cell. By employing a novel estimate for the errors incurred in this process, I minimise the computational effort required for a given accuracy and obtain a well-behaved distribution of force errors. For relative force errors of ?10?7, the computational costs exhibit an empirical scaling of ? N 0.87 . My implementation (running on a 16 core node) out-performs a GPU-based direct summation with comparable force errors for N ? 10 5 .
methods: numerical methods: n-body simulations