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

**Astronomy: Formation of Galaxies**

- Questions to be asked:
- Is the universe expanding?
- How much "dark matter" is out there?

- Is the universe expanding?
- Forces are gravitational
- State of the art of simulations:
As of 1994, about 10
^{7}bodies running for 10^{3}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): 10
^{6}bodies for 10^{4}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"

__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(n
^{2}). - This is inefficient for systems with 10
^{6}+ 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".

- Invented around 1988.
- Is related to multigrid methods.

__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.

...

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.

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