Project: $n$-Body Simulation

Background

An $n$-body simulation is a physical simulation of a system where forces (such as gravity) are exercises upon one another. This can be used to model how planets orbit the sun or how galaxies collide.

In a classical setting, this involves solving an ordinary differential equation with an initial value that describes the state (i.e. position $\overrightarrow{x_i}$ for each body $i$) of the system depending on the time $t$: $$\frac{{\mathrm{d}}^2\overrightarrow{x_i}}{\mathrm{d}t}=G\sum _{j\ne i}{m}_j\frac{{\overrightarrow{x}}_j-{\overrightarrow{x}}_i}{{|{\overrightarrow{x}}_j-{\overrightarrow{x}}_i|}^3}$$

where G is Newton's gravitational constant and $m_i$ is the (fixed) mass of every body $i$. This is of course a simplified model that doesn't take collisions, resistance or relativity into account.

For more than three bodies there is no analytical solution and we have to use numerical methods to approximate the state of the system at each time step based on the initial state.

Implementation

The sequential, template solution uses the leapfrog integration method to solve the system of equations, given an initial value that specifies the position and velocity of each body. In our case, the algorithm iterates over time in fixed time steps $\mathrm{\Delta }t$ and updates the coordinates based on the current velocity and the velocity the gravitational influence based on the positions of the other bodies in the system. The complexity of this operation is clearly in each step of the simulation.

It is obvious that we cannot parallelize the iterative steps, but what we can do is within each step try to distribute the computational load of updating the position and velocity of each body.

The template solution writes out the positions at every sampled (-s) timestep to standard out. The scripts in the examples/ directory can be use to call the program with the right parameters and convert this output into an animation.