The fast multipole algorithm

Accurate computation of the mutual interactions of N particles through electrostatic or gravitational forces has impeded progress in many areas of simulation science. The fast multipole algorithm (FMA) provides an efficient scheme for reducing computational complexity. Researchers are studying very large astrophysical simulations with hybrids of the FMA and the earlier Barnes-Hut scheme (J.E. Barnes and P. Hut, 1986). In the biophysical-simulation world, the Ewald summation method is an additional competitor. Since the development of the FMA, scientists have created various fast versions of the nearly 80-year-old Ewald method that are faster than multipole codes in some cases, although their error behavior is harder to quantify. The Ewald codes also handle periodic boundary conditions automatically; FMA-derived codes can be extended to this case with extra effort. None the less, FMA and its offspring remain important, and the newest formulations promise to again challenge Ewald codes for the title of fastest electrostatic solver