__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
In mathematics, a Green's function is the impulse response of an inhomogeneous linear differential operator defined on a domain with specified initial conditions or boundary conditions.
This means that if \operatorname is the linear differenti ...
using a
multipole expansion, which allows one to group sources that lie close together and treat them as if they are a single source.
The FMM has also been applied in accelerating the
iterative solver
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...
in the
method of moments (MOM) as applied to
computational electromagnetics problems. The FMM was first introduced in this manner by
Leslie Greengard
Dr. Leslie F. Greengard is an American mathematician, physicist and computer scientist. He is co-inventor with Vladimir Rokhlin Jr. of the fast multipole method (FMM) in 1987, recognized as one of the top-ten algorithms of the 20th century.
Gree ...
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
to
in finite arithmetic, i.e., given a tolerance
, the matrix-vector product is guaranteed to be within a tolerance
The dependence of the complexity on the tolerance
is
, i.e., the complexity of FMM is
. 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
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s 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
In computational physics and chemistry, the Hartree–Fock (HF) method is a method of approximation for the determination of the wave function and the energy of a quantum many-body system in a stationary state.
The Hartree–Fock method often ...
and
density functional theory
Density-functional theory (DFT) is a computational quantum mechanical modelling method used in physics, chemistry and materials science to investigate the electronic structure (or nuclear structure) (principally the ground state) of many-body ...
calculations in
quantum chemistry
Quantum chemistry, also called molecular quantum mechanics, is a branch of physical chemistry focused on the application of quantum mechanics to chemical systems, particularly towards the quantum-mechanical calculation of electronic contributions ...
.
See also
*
Barnes–Hut simulation
The Barnes–Hut simulation (named after Josh Barnes and Piet Hut) is an approximation algorithm for performing an ''n''-body simulation. It is notable for having order O(''n'' log ''n'') compared to a direct-sum algorithm which would b ...
*
Multipole expansion
*
''n''-body simulation
References
External links
*Gibson, Walton C. ''The Method of Moments in Electromagnetics''. Chapman & Hall/CRC, 2008.
Abstract of Greengard and Rokhlin's original paperA short course on fast multipole methodsby Rick Beatson and Leslie Greengard.
JAVA Animation of the Fast Multipole MethodNice animation of the Fast Multipole Method with different adaptations.
Free software
Puma-EMA high performance, parallelized, open source Method of Moments / Multilevel Fast Multipole Method electromagnetics code.
The Kernel-Independent Fast Multipole 3d Method (kifmm3d) is a new FMM implementation which does not require the explicit multipole expansions of the underlying kernel, and it is based on kernel evaluations.
FastBEMFree fast multipole boundary element programs for solving 2D/3D potential, elasticity, stokes flow and acoustic problems.
FastFieldSolversmaintains the distribution of the tools, called FastHenry and FastCap, developed at M.I.T. for the solution of Maxwell equations and extraction of circuit parasites (inductance and capacitance) using the FMM.
ExaFMMExaFMM is a CPU/GPU capable 3D FMM code for Laplace/Helmholtz kernels that focuses on parallel scalability.
ScalFMMScalFMM is a C++ software library developed at
Inria
The National Institute for Research in Digital Science and Technology (Inria) () is a French national research institution focusing on computer science and applied mathematics.
It was created under the name ''Institut de recherche en informatiq ...
Bordeaux with high emphasis on genericity and parallelization (using
OpenMP
OpenMP (Open Multi-Processing) is an application programming interface (API) that supports multi-platform shared-memory multiprocessing programming in C, C++, and Fortran, on many platforms, instruction-set architectures and operating syste ...
/
MPI).
DASHMMDASHMM is a C++ Software library developed at Indiana University using Asynchronous Multi-Tasking HPX-5 runtime system. It provides a unified execution on shared and distributed memory computers and provides 3D Laplace, Yukawa, and Helmholtz kernels.
RECFMMAdaptive FMM with dynamic parallelism on multicores.
{{Portal bar, Mathematics, Physics, Astronomy
Numerical analysis
Numerical differential equations
Computational science