The
N-Body Problem is well known in the scientific community. Succinctly, this involves
computing the
gravitational
potential amongst N
masses. Obviously, when the number N grows to be
large (thousands, millions), the
pairwise computation time grows as N*N.
When N is greatly large, it may be extremely time consuming or impossible to perform such a calculation. The Fast Multipole Method, likely one of the most important algorithms invented in the 20th century, alleviates this problem by presenting an approximate, though error-controllable, method of solving such a problem in O(N) time.
The basic idea behind the FMM is to expand the equation describing the gravitation potential of a point into a set of wavefunctions. Combining the wavefunctions of a pair of source and receive points yields the potential of the 2-mass system.
As wavefunctions must be truncated numerically after some number of modes (to make it numerically tractable), the resulting expression is usually valid at or greater than some distance D between points. This distance is usually referred to the "far zone". Such expansions are studied extensively so that the amount of error introduced into the computation is known and controllable.
The advantage of this method is in the superposition of "outgoing" wavefunctions of groups of nearby particles. This allows treatment these groups as a single particle, which can then be interacted with all other groups that are considered to be "far away". The results in an incredible speedup when there are many particles. Interactions between groups considered to be too close together is done in the traditional manner.
The idea of the Fast Multipole Method has also been applied to the vector Helmholtz Equation in electromagnetics, allowing for a waveform expansion of the three-dimensional Green's Function. Combined with the matrix technique known as the Method of Moments used in solving the integral equations of scattering, the resulting computational complexity is greatly reduced, allowing for the solution of matrix equations of unprecedented size.