The Fast Multipole Method (FMM) was dubbed one of the "Top 10 algorithms" of the 20th century by SIAM editors, along with other household names such as the Monte Carlo method, Quicksort, and Krylov subspace iterative methods. The FMM addresses the high computation cost for pairwise interactions in specific N-body problems in many areas of physics, for example electrostatic potentials of charged particles or gravitational forces among stars and galaxies. The problem, which naively computes O(N^2) pairs of interactions, can be reduced to O(N) using the multipole expansion as an approximation for far interactions. The method comes with clear error bounds for the approximation and allows for many subsequent extensions. In this talk, I will walk through the main theorems in Greengard and Rocklin's original paper in 1987[1], explain the algorithm, and give a survey of several generalizations of this algorithm that allows it to be applied to a wide range of problems.

[1] L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, 73, 325, (1987)