Metraipolis › archive › dc_57792ad4e56e

Fast multipole method — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Fast_multipole_method
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T11:27:36.411Z
SHA-256 of the archived text: 983247a356ddb5f2b471bc579ebf5fbb4da27308dcd095dea23c4f4a5757d5e6
Stable URL of this page: https://metraipolis.com/documento/dc_57792ad4e56e

How to cite

Fast multipole method — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Fast_multipole_method (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_57792ad4e56e (Metraipolis archive dc_57792ad4e56e, sha256 983247a356ddb5f2b471bc579ebf5fbb4da27308dcd095dea23c4f4a5757d5e6)

BibTeX

@misc{dc57792ad4e56e,
  title = {Fast multipole method — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Fast_multipole_method},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_57792ad4e56e; sha256 983247a356ddb5f2b471bc579ebf5fbb4da27308dcd095dea23c4f4a5757d5e6},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Fast_multipole_method. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 O ( N 2 ) {\displaystyle {\mathcal {O}}(N^{2})} to O ( N ) {\displaystyle {\mathcal {O}}(N)} in finite arithmetic, i.e., given a tolerance ε {\displaystyle \varepsilon } , the matrix-vector product is guaranteed to be within a tolerance ε . {\displaystyle \varepsilon .} The dependence of the complexity on the tolerance ε {\displaystyle \varepsilon } is O ( log ( 1 / ε ) ) {\displaystyle {\mathcal {O}}(\log(1/\varepsilon ))} , i.e., the complexity of FMM is O ( N log ( 1 / ε ) ) {\displaystyle {\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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Numerical analysis»).
Fonte: Wikipedia in inglese, voce «Fast multipole method» — https://en.wikipedia.org/wiki/Fast_multipole_method
Wikidata Q5437040 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5437040
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Fast_multipole_method?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1369241924, consultata il 2026-10-07T11:16:51.760Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 2be0fa350b680fe5ba04596e213dcf1d930814981b581c271d920cc6f0308933