ITR/ACS: Self-Scheduling N-Body Algorithms

Principal Investigator: Lars S. Nyland
Co-Principal Investigators: Jan Prins
Funding Agency: National Science Foundation
Agency Number: ACI-0082931

Abstract
A new, innovative approach to solving the N-body problem is proposed, called *self-scheduling N-body algorithms*. It is a multiple time step method where each pairwise interaction is evaluated using a dynamic schedule that attempts to equalize the error of each interaction, drastically reducing the computational cost. Starting from this basic idea, a family of algorithms is defined that trade computational cost with implementation complexity and memory use. The benefits of this family of algorithms are not only reduced computational complexity, but also a straightforward implementation.

All N-body simulations use discrete time steps to simulate the motion of the particles. The forces on a particle are applied for the time step as an impulse that advances the simulation to the next time step. Instead of using a fixed time step for all interactions (which is too conservative for most interactions), an approach that equalizes impulse is proposed. This is a fundamentally new and different way of approaching the N-body problem and has the potential to yield very fast algorithms. Mathematically, the constant time step T is traded for constant impulse, I, defined as F[i,j] * T[i,j], where F[i,j] is the force between particles i and j, and T[i,j] becomes the time step used to re-evaluate F[i,j]. Using a constant impulse instead of a constant time step leads to an expected execution complexity ofO(n * cuberoot(n)) per simulation step. Algorithmic improvements that rely on the first and second derivatives of force reduce the per step computational complexity to O(n log n) andO(n) respectively.