The Fast Multipole Algorithm is an algorithm for computing the potential field (either gravitational or electrical) created by a set of interacting bodies (atoms, planets, stars). It was developed by Leslie Greengard [Greengard87, MIT Press] and is very complex, using multipole expansions and operators to compute the field. It is also potentially faster than other N-body algorithms, it has an asymptotic complexity of O(N), where others are believed to have complexities O(N log N) or O(N^2).
It is known that the FMA has a large constant factor, a fact that allows all other methods to outperform the FMA for small numbers of bodies. It is now known at what point the FMA outperforms the other well-known methods. The algorithm is also complex enough so that the existing parallel implementations work best for uniform distributions of bodies, degrading as the distribution becomes non-uniform. There are no parallel implementations, other than this one, that implement the 3D FMA in parallel.
There are some research papers available about our implementation: Prototyping Parallel Algorithms, A Data-Parallel Implementation of the Fast Multipole Algorithm, and Spatial Decompositions For Hierarchical N-Body Simulations .
The source code for several versions of our implementation are also available.