N-Body computations are a family of computation that models a set of particles (known as bodies), each of which must consider all the other bodies during the computation. Example applications of N-Body include (but are not limited to) the following.
• Gravitational simulation in which stars exert gravitational forces
• Molecular modeling in which ions exert electrostatic forces
• Particle systems in computer graphics to simulate water and fire
• “Boids,” a technique for computer animation designed to simulate flocking behavior
Typically the paths of the bodies are being simulated per timestep, and computing each timestep costs O(N2) operations for N bodies. In most formulations, the forces quickly decrease with distance, leading ...