Fast Multipole Method
Fast Multipole Method (FMM) · Also known as: FMM, multipole acceleration, hierarchical method
The Fast Multipole Method (FMM) is a hierarchical algorithm that reduces the computational complexity of particle interactions from O(n²) to O(n log n) or O(n), developed by Greengard and Rokhlin in 1987. By grouping distant particles and approximating their cumulative effects via multipole expansions, FMM enables efficient simulation of N-body problems, boundary integral equations, and Coulomb interactions.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use FMM for large-scale N-body problems (molecular dynamics, astrophysics), boundary element methods on complex geometries, Coulomb interactions in electrostatics, and gravitational simulations. Essential when n > 10,000. For smaller problems or short-range interactions, direct computation or Barnes-Hut tree is simpler. Requires translation operators; kernel-independent methods generalize to arbitrary kernels.
Strengths & limitations
- Reduces computational complexity from O(n²) to O(n) or O(n log n), enabling billion-particle simulations
- Provably accurate: truncation error controlled via multipole order p; increasing p always improves accuracy
- Parallelizable: tree structure and independent cell computations suit distributed and GPU acceleration
- Mathematically rigorous: grounded in classical potential theory and harmonic analysis
- Complex implementation: requires careful handling of multipole-to-local translations, special functions, and tree management
- High memory overhead: storing tree, expansions, and particle lists increases constant factors
- Problem-dependent: translation operators must be computed for each kernel; not universal without kernel-independent variants
- Loses efficiency for non-uniform distributions; dense clusters require adaptive refinement with added overhead
Frequently asked
What is a multipole expansion and why does truncation give controlled error?
A multipole expansion approximates potential from a distribution as Σ M_p r^{-p-1} P_p(cos θ), where M_p are moments. Truncating at order P_max gives error O(r^{-P_max-1}); doubling P halves error exponentially, not linearly.
How do I choose the multipole truncation order p?
Use the thumb rule: p ≈ -log₁₀(tolerance) + O(1). For 10^{-6} accuracy, p ≈ 6-8. For 10^{-12}, p ≈ 12-14. Run tests: compare FMM with p and p+2; if results match to tolerance, p is adequate.
What is the near-field/far-field distinction and how do I set the threshold?
Far-field: particles separated by distance > θ × (cell size); use multipole expansion. Near-field: distance ≤ θ × (cell size); compute directly. Typical θ = 1–2; larger θ means more far-field acceleration but higher near-field cost. θ depends on desired error tolerance.
Why is FMM hard to parallelize compared to direct O(n²) computation?
FMM's tree structure creates load imbalance: deep levels have many cells (good parallelism) but are memory-limited; shallow levels have few cells. Collective communication for moment aggregation (upward pass) becomes a bottleneck. Modern approaches use space-filling curves or domain decomposition for better scaling.
Sources
- Greengard, L., & Rokhlin, V. (1987). A fast algorithm for particle simulations. Journal of Computational Physics, 73(2), 325–348. DOI: 10.1016/0021-9991(87)90140-9 ↗
- Greengard, L. (1988). The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press. ISBN: 0262071088
- Ying, L., Biros, G., & Zorin, D. (2004). A kernel-independent adaptive fast multipole method. Journal of Computational Physics, 196(2), 591–626. link ↗
How to cite this page
ScholarGate. (2026, June 3). Fast Multipole Method (FMM). ScholarGate. https://scholargate.app/en/numerical-methods/fast-multipole-method
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Boundary Element MethodMaterials Science↔ compare