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 are a single source.[1]
The FMM has also been applied in accelerating the iterative solver in the method of moments (MOM) as applied to computational electromagnetics problems,[2] and in particular in computational bioelectromagnetism. The FMM was first introduced in this manner by Leslie Greengard and Vladimir Rokhlin Jr.[3] 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 algorithms of the 20th century.[4] 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.
^Rokhlin, Vladimir (1985). "Rapid Solution of Integral Equations of Classic Potential Theory." J. Computational Physics Vol. 60, pp. 187–207.
^Nader Engheta, William D. Murphy, Vladimir Rokhlin, and Marius Vassiliou (1992), “The Fast Multipole Method for Electromagnetic Scattering Computation,” IEEE Transactions on Antennas and Propagation 40, 634–641.
^"The Fast Multipole Method". Archived from the original on 2011-06-03. Retrieved 2010-12-10.
^Cipra, Barry Arthur (May 16, 2000). "The Best of the 20th Century: Editors Name Top 10 Algorithms". SIAM News. 33 (4). Society for Industrial and Applied Mathematics: 2. Retrieved February 27, 2019.
and 22 Related for: Fast multipole method information
The fastmultipolemethod (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the n-body problem. It...
This formulation is naturally combined with fastmultipolemethod (FMM) acceleration, and the entire method is known as charge-based BEM-FMM. The combination...
The multilevel fastmultipolemethod (MLFMM) is used along with method of moments (MoM) a numerical computational method of solving linear partial differential...
Charge based boundary element fastmultipolemethod. FMM can also be used to accelerate MoM. While the fastmultipolemethod is useful for accelerating MoM...
A multipole expansion is a mathematical series representing a function that depends on angles—usually the two angles used in the spherical coordinate...
Maxwell problems utilizing a fastmultipolemethod for compression and reduction of computational cost boundary-element-method.com An open-source BEM software...
communication requirements for parallel computing with the help of a fastmultipolemethod. A wavelet-based approximate FFT by Guo and Burrus (1996) takes...
computer scientist. He is co-inventor with Vladimir Rokhlin Jr. of the fastmultipolemethod (FMM) in 1987, recognized as one of the top-ten algorithms of the...
Barnes–Hut simulation, the fastmultipolemethod. Following the work by Munjiza and Owen, the combined finite-discrete element method has been further developed...
breakthrough came in the 1980s with the development of the Barnes-Hut and fastmultipolemethod (FMM) algorithms. These paved the way to practical computation of...
{\displaystyle T} in O ( m 2 ) {\displaystyle O(m^{2})} operations. The FastMultipoleMethod can compute all eigenvalues in just O ( m log m ) {\displaystyle...
interactions. Advanced algorithms, such as the Ewald summation or FastMultipoleMethod, reduce this to O ( N log N ) {\displaystyle {\mathcal {O}}(N\log...
with this form seeing some usage in the literature regarding the fastmultipolemethod. Conversion between these two forms can be easily achieved using...
computed solution to refine the mesh only where necessary Fastmultipolemethod — hierarchical method for evaluating particle-particle interactions Perfectly...
uses method of moments (integral equations) and FEMs to compute capacitive, conductance, inductance and resistance matrices. It uses the fastmultipole method...
order O(n log n) instead of O(n2) as in a direct-sum simulation. Fastmultipolemethod (FMM): speeds up the calculation of long-ranged forces Rainflow-counting...
fluctuations in density may be treated more efficiently with the fastmultipolemethod of Greengard and Rokhlin. The electrostatic energy of a polar crystal...
computational physics, Vassiliou is known for the introduction of Rokhlin's fastmultipolemethod to computational electromagnetics. As an executive at the Rockwell...
computationally too expensive to simulate large-scale problems. The fastmultipolemethod (FMM) can reduce both CPU time and memory requirement from O(N2)...
multiplication with O ( n log n ) {\displaystyle O(n\log n)} ops (e.g. the fastmultipolemethod), (pivoted) LU factorization with O ( n 2 ) {\displaystyle O(n^{2})}...
Global Information
