Fast multipole method

Summary

The fast multipole method computes all pairwise interactions among $N$ particles, such as gravitational or electrostatic potentials. It needs $O(N)$ operations for a prescribed accuracy, instead of $O(N^2)$. It groups the particles in a tree of boxes and replaces the field of each distant group by a truncated multipole expansion. It was introduced by Greengard and Rokhlin in 1987. It speeds up n-body simulations and the matrix-vector products of integral-equation solvers such as the method of moments. It is also a model for hierarchical matrices.