When studying the evolution of particle systems, whereas it be on atomic or cosmological scale, N-body simulations have proved to be a useful, and powerful, tool. If the particles can be considered as point masses, and preferably collisionless, such simulations have given very accurate results. The classical N-body problem simulates the evolution of a system of N bodies, where the force exerted on each body arises due to its interaction with all the other bodies in the system. N-body algorithms have numerous applications in areas such as molecular dynamics, plasma physics, and astrophysics. In astrophysics they have been used to study such diverse topics as planetary formation, star cluster dynamics, interacting galaxies, and even cosmological modeling.
In an N-body algorithm one calculates the force which acts on one particle from all the other particles in the system. The simulation proceeds over time-steps, each time computing the net force on every body, and thereby updating its position and other attributes. For a system where gravitation is the dominating force, the basic approach is that starting with the masses, positions and velocities of N particles at a given time, one can calculate, by numerically solving the equation of motion, the state of the system at any subsequent time. Doing this, one can get a good representation of the movements, the trajectories, of these particles. The main problem with this method, is that there is a limitation to the value of N due to computer time required to calculate the forces.
When having a relative small number of particles, i.e. 
, direct summation
is possible without making use of an impossible amount of CPU time. The method used is
often known as ``particle-particle'' or PP scheme, where the force on a particle is
calculated by directly summing the inverse square force law due to all other particles.
About 
operations are required to evaluate the force on N particles from the
other N-1 particles, and hence the computing time increases very rapidly with N.
Nevertheless, the major cause for long computation time is the enormous difference in
time scale from one particle to another, dependent on the distance between the particles.
If particles gets close to each other, the velocities of the particles change very
rapidly, whereupon correspondingly small time-steps is needed to follow their
trajectories accurately. If there is no distinction between the time scales, the orbits
of the more slowly varying particles will then be calculated at equally small,
redundant, time-steps. A way to mend this problem is simply preventing the particles
getting too close to each other by using a softening parameter. The strict 
force
law is then replaced by a smoothed version, 
, where c is the cutoff.
Softening, and other methods, leads to a reduction of the computing time for the PP
scheme, but not enough to make it usable for systems with large number of particles.
A significant gain in N can be obtained by calculating the force acting on a particle from a potential obtained by solving the Poisson equation on a mesh, instead of considering each particle individually. The ``particle-mesh'' or PM scheme adopts such an approach. There is an enormous reduction in computing time using this scheme opposed to the PP scheme, but it is at the cost of resolution in the evaluation of the force field. This scheme is therefore often used for systems in which the potential only varies at large scales, for example in HDM models.
A third scheme has been developed, namely the ``particle-particle-particle-mesh'' or the
scheme. This method tries to combine the advantages of both the PP and PM
methods. The basic idea is to split up the interparticle forces into two parts: a short
range, rapidly varying, part due to nearby particles and a slowly varying part due to
more widely separated particles. The PP method is used to determine the former and the
PM scheme the latter; thus, one can evaluate the short range forces accurately and the
long range forces rapidly. Due to the direct summations of the close range forces, the
scheme is slower than the PM scheme, but faster than the PP scheme. The
has been extensively used in cosmological simulations of CDM models.