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 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 matrix-vector product in an iterative solver from O(N^2) to O(N\log 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 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
• 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.
• The Fast Multipole Method A somewhat detailed overview of the FMM.
• 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