Fast Multipole Method
Encyclopedia
The fast multipole method (FMM) is a mathematical 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 are 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. The FMM was first introduced in this manner by Greengard
and Rokhlin
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) to O(N). This has expanded the area of applicability of the MOM to far greater problems than were previously possible.
The FMM, introduced by Rokhlin and Greengard, has been acclaimed as one of the top ten algorithms of the 20th century. The FMM algorithm dramatically 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 Hartree–Fock and density functional theory
calculations in quantum chemistry
.
N-body problem
The n-body problem is the problem of predicting the motion of a group of celestial objects that interact with each other gravitationally. Solving this problem has been motivated by the need to understand the motion of the Sun, planets and the visible stars...
. It does this by expanding the system Green's function
Green's function (many-body theory)
In many-body theory, the term Green's function is sometimes used interchangeably with correlation function, but refers specifically to correlators of field operators or creation and annihilation operators....
using a multipole expansion
Multipole expansion
A multipole expansion is a mathematical series representing a function that depends on angles — usually the two angles on a sphere. These series are useful because they can often be truncated, meaning that only the first few terms need to be retained for a good approximation to the original...
, 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 the method of moments
Boundary element method
The boundary element method is a numerical computational method of solving linear partial differential equations which have been formulated as integral equations . It can be applied in many areas of engineering and science including fluid mechanics, acoustics, electromagnetics, and fracture...
(MOM) as applied to computational electromagnetics
Computational electromagnetics
Computational electromagnetics, computational electrodynamics or electromagnetic modeling is the process of modeling the interaction of electromagnetic fields with physical objects and the environment....
problems. The FMM was first introduced in this manner by Greengard
Leslie Greengard
Leslie F. Greengard is an American mathematician, doctor of medicine and computer scientist. He is co-inventor of the fast multipole method in 1987, recognised as one of the top-ten algorithms of the 20th century....
and Rokhlin
Vladimir Rokhlin (American scientist)
Vladimir Rokhlin is mathematician and professor of computer science and mathematics at the Yale University. He is co-inventor of the fast multipole method in 1987, recognised as one of the top-ten algorithms of the 20th century.-Short biography:Vladimir Rokhlin was born on August 4, 1952 in...
and is based on the multipole expansion
Multipole expansion
A multipole expansion is a mathematical series representing a function that depends on angles — usually the two angles on a sphere. These series are useful because they can often be truncated, meaning that only the first few terms need to be retained for a good approximation to the original...
of the vector Helmholtz equation
Helmholtz equation
The Helmholtz equation, named for Hermann von Helmholtz, is the elliptic partial differential equation\nabla^2 A + k^2 A = 0where ∇2 is the Laplacian, k is the wavenumber, and A is the amplitude.-Motivation and uses:...
. 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) to O(N). This has expanded the area of applicability of the MOM to far greater problems than were previously possible.
The FMM, introduced by Rokhlin and Greengard, has been acclaimed as one of the top ten algorithms of the 20th century. The FMM algorithm dramatically 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 Hartree–Fock and density functional theory
Density functional theory
Density functional theory is a quantum mechanical modelling method used in physics and chemistry to investigate the electronic structure of many-body systems, in particular atoms, molecules, and the condensed phases. With this theory, the properties of a many-electron system can be determined by...
calculations in quantum chemistry
Quantum chemistry
Quantum chemistry is a branch of chemistry whose primary focus is the application of quantum mechanics in physical models and experiments of chemical systems...
.
External Links
- Gibson, Walton C. The Method of Moments in Electromagnetics. Chapman & Hall/CRC, 2008. ISBN 978-1-4200-6145-1
- FEKO from EM Software & Systems includes the Multilevel FMM as solution option.
- Serenity A high-fidelity Radar Cross Section (RCS) code that uses the Moment Method and the FMM.
- Abstract of Greengard and Rokhlin's original paper
- A short course on fast multipole methods by Rick Beatson and Leslie Greengard.
- JAVA Animation of the Fast Multipole Method Nice animation of the Fast Multipole Method with different adaptations.
Free software
- Puma-EM A high performance, parallelized, open source Method of Moments / Multilevel Fast Multipole Method electromagnetics code
- KIFMM3d 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.
- PetFMM PetFMM is a parallel, extensible fast multipole library for N-body interactions, built on the framework of PETSc.
- FastFieldSolvers FastFieldSolvers consists of tools developed at M.I.T. for the solution of Maxwell equations and extraction of circuit parasites (inductance and capacitance).