Fast multipole method

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] 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.

See also

References
  1. Rokhlin, Vladimir (1985). "Rapid Solution of Integral Equations of Classic Potential Theory." J. Computational Physics Vol. 60, pp. 187–207.
  2. 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.
  3. "Archived copy". Archived from the original on 2011-06-03. Retrieved 2010-12-10.CS1 maint: archived copy as title (link)
  4. Cipra, Barry Arthur (May 16, 2000). "The Best of the 20th Century: Editors Name Top 10 Algorithms". SIAM News. Society for Industrial and Applied Mathematics. 33 (4): 2. Retrieved February 27, 2019.

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.
  • FastBEM Free fast multipole boundary element programs for solving 2D/3D potential, elasticity, stokes flow and acoustic problems.
  • FastFieldSolvers maintains 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.
  • ExaFMM ExaFMM is a CPU/GPU capable 3D FMM code for Laplace/Helmholtz kernels that focuses on parallel scalability.
  • ScalFMM ScalFMM is a C++ software library developed at Inria Bordeaux with high emphasis on genericity and parallelization (using OpenMP/MPI).
  • DASHMM DASHMM 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.
  • RECFMM Adaptive FMM with dynamic parallelism on multicores.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.