Fast multipole method - Wikipedia

Abstraction: O(N) algorithm for computing long-range N-body force interactions

Key points:

• FMM reduces N-body interaction computation from O(N^2) to O(N) by grouping distant sources via multipole expansion
• Introduced by Rokhlin and Greengard; named one of the top 10 algorithms of the 20th century (SIAM, 2000)
• Reduces MoM matrix-vector products in computational electromagnetics from O(N^2) to O(N log(1/eps))
• Memory savings: far-field matrix elements need not be explicitly stored
• Applied in quantum chemistry (Hartree-Fock, DFT Coulomb integrals) and bioelectromagnetism
• Key insight: if source and target are well-separated, the interaction kernel is well-approximated by a polynomial via Chebyshev interpolation

Connections: Numerical Methods · N Body Problem · Fast Multipole Method

Source: http://en.wikipedia.org/wiki/Fast_multipole_method