N-Body Simulations

N-Body Simulations


The goal of N-Body problems is to determine the motion over time of bodies (particles) due to forces from other bodies. Typical calculated forces include electrostatic force and gravity. The basic method used for solving the problem is to loop forever, stepping discretely through time and doing the following at each timestep:

Our focus will be on methods for calculating the forces. Note that it is possible to use multiple resolutions for time, i.e. different delta(t) for different particles, but we will only consider uniform delta(t).


Astronomy: Formation of Galaxies

Biology/Chemistry: Molecular Dynamics



Particle-Particle (the naive method)

This method simply calculates the force between all pairs of particles.

Mesh-Based Methods

The following figure shows Mesh-based N-body methods:

Particle Mesh (PM): Breaks space into a uniform mesh and places each particle in the appropriate cell of the mesh. It uses a discrete Fourier transforms (DFT) to solve a partial differential equation (PDE) over the mesh.

Particle-Particle Particle-Mesh (P3M): A combination of direct particle interaction for close particles and the particle-mesh method for distant particles.

Nested-Grid Particle-Mesh (NGPM): uses a nested mesh with different "resolutions".

Tree Based Methods

Top-down particle-cell: Divides space into a quadtree (2 dimensional) or octree (3 dimensional). When a cell (inner node of the quad or octree) is far enough away from a particle we can calculate the force to the center of mass of the cell instead of having to calculate the force to each particle in the cell.

For example, in the following diagram the particle in the upper left could group the two particles in the lower right together and calculate the force to their center-of-mass.

Bottom-up particle-cell: Similar to the top-down method but the tree is created bottom-up by grouping neighboring particles or cells, as shown in the following diagram.

Cell-cell (Fast multipole method, FMM): Also uses a tree but allows for "cell-cell interactions" as well as "particle-cell interactions".

Tree-code particle-mesh: Mixes ideas from particle-mesh methods and tree-based methods.

Mesh-based Algorithms


Tree-based Algorithms

The approach taken by tree based algorithms is to approximate far away particles by some sort of center of mass rather than by direct interactions. The further away you are from a set of points, the more you can group together and consider as a center-of-mass. These "centers of mass" are then organized hierarchically (in a tree) so that the approaches can determine which sets of points to approximate by their centers of mass. The root of the tree will include all the particles, and at each node of the tree the children will partition the set of particles of that node, usually by partitioning the space taken by that node. The close you are to the points, the further down in the tree you will need to go so that you will consider smaller sets of particles.

We will call a set of particles grouped together with a center of mass, a cell. In the algorithms we will consider 3 types of interactions:

These interactions are shown in the following diagram.

Here, we only outline the top-down tree-based algorithms.

Barnes-Hut Algorithm

The first tree-based algorithm we consider is the Barnes-Hut algorithm, which uses particle-particle and particle-cell interactions, but no cell-cell interactions.