Fast Multipole Method

Fast Multipole Method

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 [http://www-theor.ch.cam.ac.uk/people/ross/thesis/node97.html] 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 explicitly stored, resulting in a tremendous savings in the required system memory. If the FMM is then applied in a hierarchical manner, it can improve the complexity matrix-vector product in an iterative solver from O(N^2) to O(Nlog 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 greatest 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 Kohn-Sham Density functional theory calculations in quantum chemistry.

References and external links

*Gibson, Walton C. "The Method of Moments in Electromagnetics". Chapman & Hall/CRC, 2008. ISBN 978-1-4200-6145-1
* [http://www.feko.info/ FEKO] from EM Software & Systems includes the Multilevel FMM as solution option.
* [http://www.radarsoftware.com Serenity] A high-fidelity Radar Cross Section (RCS) code that uses the Moment Method and the FMM.
* [http://portal.acm.org/citation.cfm?id=36901 Abstract of Greengard and Rokhlin's original paper]
* [http://math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf A short course on fast multipole methods] by Rick Beatson and Leslie Greengard.
* [http://www-theor.ch.cam.ac.uk/people/ross/thesis/node97.html The Fast Multipole Method] A somewhat detailed overview of the FMM.
* [http://www.umiacs.umd.edu/~wpwy/fmm/ JAVA Animation of the Fast Multipole Method] Nice animation of the Fast Multipole Method with different adaptations.

Free Software

* [http://sourceforge.net/projects/puma-em/ Puma-EM] A high performance, parallelized, open source Method of Moments / Multilevel Fast Multipole Method electromagnetics code


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • 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… …   Wikipedia

  • Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group …   Wikipedia

  • 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 (i.e. in boundary integral form). It can be applied in many areas of engineering and …   Wikipedia

  • Discrete element method — A discrete element method (DEM), also called a distinct element method is any of family of numerical methods for computing the motion of a large number of particles of micrometre scale size and above. Though DEM is very closely related to… …   Wikipedia

  • Discrete element method — Mit Discrete Element Method (DEM) wird eine 1979 von Cundall und Strack entwickelte numerische Berechnungsmethode bezeichnet, mit der die Bewegung einer großen Zahl von Teilchen berechnet werden kann. Die Methode wird manchmal auch als Distinct… …   Deutsch Wikipedia

  • Distinct element method — Mit Discrete Element Method (DEM) wird eine 1979 von Cundall und Strack entwickelte numerische Berechnungsmethode bezeichnet, mit der die Bewegung einer großen Zahl von Teilchen berechnet werden kann. Die Methode wird manchmal auch als Distinct… …   Deutsch Wikipedia

  • Discrete Element Method — Mit Discrete Element Method (DEM) wird eine 1979 von Cundall und Strack entwickelte numerische Berechnungsmethode bezeichnet, mit der die Bewegung einer großen Zahl von Teilchen berechnet werden kann. Die Methode wird manchmal auch als Distinct… …   Deutsch Wikipedia

  • Distributed multipole analysis — (DMA) is a compact and accurate way of describing the spatial distribution of electric charge within a molecule. The DMA method was devised by Prof. Anthony Stone of Cambridge University to describe the charge distribution of a molecule in terms… …   Wikipedia

  • 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. It typically involves using computationally… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”