Fast multipole method

---

title: "Fast multipole method" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["numerical-analysis", "numerical-differential-equations", "computational-science"] description: "Numerical technique" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Fast_multipole_method" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Numerical technique ::

NOTOC The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the n-body problem. It does this by expanding the system Green's function using a multipole expansion, which allows one to group sources that lie close together and treat them as if they were a single source.

The FMM has also been applied in accelerating the iterative solver in the method of moments (MOM) as applied to computational electromagnetics problems, and in particular in computational bioelectromagnetism. The FMM was first introduced in this manner by Leslie Greengard and Vladimir Rokhlin Jr. and is based on the multipole expansion of the vector Helmholtz equation. By treating the interactions between far-away basis functions using the FMM, the corresponding matrix elements do not need to be explicitly stored, resulting in a significant reduction in required memory. If the FMM is then applied in a hierarchical manner, it can improve the complexity of matrix-vector products in an iterative solver from \mathcal{O}(N^2) to \mathcal{O}(N) in finite arithmetic, i.e., given a tolerance \varepsilon, the matrix-vector product is guaranteed to be within a tolerance \varepsilon. The dependence of the complexity on the tolerance \varepsilon is \mathcal{O}(\log(1/\varepsilon)), i.e., the complexity of FMM is \mathcal{O}(N\log(1/\varepsilon)). This has expanded the area of applicability of the MOM to far greater problems than were previously possible.

The FMM, introduced by Rokhlin Jr. and Greengard has been said to be one of the top ten algorithms of the 20th century. The FMM algorithm reduces the complexity of matrix-vector multiplication involving a certain type of dense matrix which can arise out of many physical systems.

The FMM has also been applied for efficiently treating the Coulomb interaction in the Hartree–Fock method and density functional theory calculations in quantum chemistry.

Sketch of the algorithm

::figure[src="https://upload.wikimedia.org/wikipedia/commons/6/6f/Fast_Multipoles_-_Local_Expansion.svg" caption="Fast multipole method – interpolation of a pole at ''x'' = 3 with an order-5 Chebyshev polynomial"] ::

In its simplest form, the fast multipole method seeks to evaluate the following function: f(y) = \sum_{\alpha=1}^N \frac{\phi_\alpha}{y - x_\alpha}, where x_\alpha \in [-1, 1] are a set of poles, and \phi_\alpha\in\mathbb C are the corresponding pole weights on a set of points {y_1, \ldots, y_M} with y_\beta \in [-1, 1]. This is the one-dimensional form of the problem, but the algorithm can be easily generalized to multiple dimensions and kernels other than (y - x)^{-1}.

Naively, evaluating f(y) on M points requires \mathcal O(MN) operations. The crucial observation behind the fast multipole method is that if the distance between y and x is large enough, then (y - x)^{-1} is well-approximated by a polynomial. Specifically, let -1 be the Chebyshev nodes of order p \ge 2, and let u_1(y), \ldots, u_p(y) be the corresponding Lagrange basis polynomials. One can show that the interpolating polynomial \frac{1}{y-x} = \sum_{i=1}^p \frac{1}{t_i - x} u_i(y) + \epsilon_p(y) converges quickly with polynomial order, |\epsilon_{p(y)}| , provided that the pole is far enough away from the region of interpolation, |x| \ge 3 and |y| . This is known as the "local expansion".

The speed-up of the fast multipole method derives from this interpolation: provided that all the poles are "far away", we evaluate the sum only on the Chebyshev nodes at a cost of \mathcal O(N p), and then interpolate it onto all the desired points at a cost of \mathcal O(M p): \sum_{\alpha=1}^N \frac{\phi_\alpha}{y_\beta - x_\alpha} = \sum_{i=1}^p u_i(y_\beta) \sum_{\alpha=1}^N \frac{1}{t_i - x_\alpha} \phi_\alpha.

Since p = -\log_5 \epsilon, where \epsilon is the numerical tolerance, the total cost is \mathcal O\big((M + N) \log(1/\epsilon)\big).

To ensure that the poles are indeed well-separated, one recursively subdivides the unit interval such that only \mathcal O(p) poles end up in each interval. One then uses the explicit formula within each interval and interpolation for all intervals that are well-separated. This does not spoil the scaling, since one needs at most \log(1/\epsilon) levels within the given tolerance.

References

References

1. Rokhlin, Vladimir (1985). "[https://www.sciencedirect.com/science/article/pii/0021999185900026 Rapid Solution of Integral Equations of Classic Potential Theory]." J. Computational Physics Vol. 60, pp. 187–207.
2. [[Nader Engheta]], William D. Murphy, [[Vladimir Rokhlin (American scientist). Vladimir Rokhlin]], and [[Marius Vassiliou]] (1992), “The Fast Multipole Method for Electromagnetic Scattering Computation,” IEEE Transactions on Antennas and Propagation 40, 634–641.
3. "The Fast Multipole Method".
4. (May 16, 2000). "The Best of the 20th Century: Editors Name Top 10 Algorithms". [[Society for Industrial and Applied Mathematics]].
5. (November 1994). "The continuous fast multipole method". Chemical Physics Letters.
6. (May 1996). "Linear scaling density functional calculations via the continuous fast multipole method". Chemical Physics Letters.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::