Fast Multipole Method
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.
Key highlights
- 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
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
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
- 1.Greengard, L., & Rokhlin, V. (1987). A fast algorithm for particle simulations. Journal of Computational Physics, 73(2), 325–348.
- 2.Greengard, L. (1988). The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press.ISBN 0262071088
- 3.Ying, L., Biros, G., & Zorin, D. (2004). A kernel-independent adaptive fast multipole method. Journal of Computational Physics, 196(2), 591–626.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Fast Multipole Method. ScholarGate. https://scholargate.app/numerical-methods/fast-multipole-method