N-Body Simulations N-Body Simulations Introduction

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:
• Update positions using velocities (x->i+1 = x->i + delta(t) v->i).

• Calculate forces F->.

• Update velocities (v->i+1 = v->i + (1/m) delta(t) F->i)

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). Applications

Astronomy: Formation of Galaxies

• Is the universe expanding?

• How much "dark matter" is out there?

• Forces are gravitational

• State of the art of simulations: As of 1994, about 107 bodies running for 103 steps, taking 1 week on 500 processors.

Biology/Chemistry: Molecular Dynamics

• Electrostatic + other forces (Bond forces, Lennard-Jones potential)

• State of the art (protein folding): 106 bodies for 104 timesteps.

• Note that it is easier to use a cutoff radius for limiting electrostatic calculations, because distant charges cancel each other out.

Others

• Plasma Physics

• Partial Differential Equations

• Fluid Dynamics - "vortex particles"

Algorithms

Particle-Particle (the naive method)

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

• The time required to calculate all interactions is O(n2).

• This is inefficient for systems with 106+ bodies. Here is an example.

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.

• These methods were invented in the 70's.

• For m cells, O(m log m) time is required.

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

• Invented in the early 80s.

• Provides better accuracy for the same time as PM.

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. • Appel (1985) produced the first tree-based solution.

• Barnes-Hut refined it in 1986.

• For n particles, O(n log n) time required (under certain assumptions).

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. • Press produced an algorithm in 1986.

• O(n log n) time is required (under certain assumptions).

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

• Incorporates four main ideas: multiple expansions, error bounds on dropping terms dual expansion, and translation of expansion.

• These are the fastest known methods for solving N-Body problems.

• Done by Greengard in 1988.

• They require O(n) time for uniform distributions. Non-uniform distributions may increase the required time.

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

• Work by Xi in 1989.

...

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:

• Particle-particle (direct interactions between 2 particles)
• Particle-cell (interaction between a particle and the center of mass of a cell)
• Cell-cell (interactions between 2 centers-of-mass)

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.

• It consists of building a tree using an oct-tree in 3-D or a quad-tree in 2-D, and then using the tree to calculate the force on each particle.

• Each division evenly splits up the space so, for example, in a quadtree each step will consists of dividing a square into 4 squares. Note that this will not necessarily evenly divide the particles, so the tree in general will not be balanced.

• The algorithm for building the tree works top down and is defined by the following code:

... The algorithm code goes in here ... saleh@npac.syr.edu