What Is MLFMA?

The Multilevel Fast Multipole Algorithm (MLFMA) is a computational method for rapidly evaluating pairwise interactions among large numbers of sources and field points, reducing the computational cost of dense matrix-vector products from O(N²) to O(N log N). It was developed specifically to address the prohibitive memory and CPU requirements that arise when solving electromagnetic scattering and radiation problems involving electrically large objects. MLFMA builds on the Fast Multipole Method (FMM) introduced by Greengard and Rokhlin in 1987, extending it to a hierarchical multilevel tree structure suitable for high-frequency wave interactions. The algorithm draws on computational physics, numerical linear algebra, and applied mathematics.

In computational electromagnetics (CEM), problems involving perfectly conducting or dielectric objects are typically formulated as surface integral equations derived from Maxwell's equations. Discretizing these equations with boundary element methods (BEM) using basis functions on triangular surface meshes leads to dense N×N matrices, where N is the number of surface unknowns. For objects spanning many wavelengths, N can reach tens of millions, making direct matrix storage and inversion impractical. MLFMA is the principal acceleration tool for iterative solvers applied to these dense systems.

Fast Multipole Method Foundation

The Fast Multipole Method groups distant source points into clusters and represents their collective field contribution through a compact multipole expansion rather than evaluating each source-field pair individually. This reduces the interaction cost between well-separated clusters to O(1), independent of the number of sources in each cluster. For low-frequency or static problems, spherical harmonic expansions serve as the expansion basis. For high-frequency wave problems relevant to electromagnetics, the expansion uses a diagonal form of the translation operator expressed as an integral over outgoing plane waves, commonly called the diagonal translation or the MLFMA translation operator. The IEEE Transactions paper introducing the multilevel fast multipole algorithm for electromagnetic scattering by Chew, Jin, and colleagues established the foundational formulation used in CEM solvers today.

Multilevel Hierarchical Structure

The multilevel extension organizes the spatial domain into an oct-tree of nested cubic cells at progressively finer levels. At each level of the tree, groups of sources in a cell are aggregated into outgoing radiation patterns. These patterns are translated from one cell to well-separated cells at the same level using the diagonal translation operator, then disaggregated into incoming patterns for field evaluation. Interactions between cells that are too close for the multipole approximation to be accurate are handled directly in the near-field, while all far-field contributions pass through the aggregation-translation-disaggregation cycle. This multilevel scheme achieves the O(N log N) scaling by avoiding redundant translation work across levels. Recent work described in a 2024 arXiv paper on MLFMA for electromagnetic scattering by large metasurfaces extends the framework to metasurface arrays by combining the tree structure with a static mode representation that further reduces the number of unknowns.

Integral Equation Formulation and Iterative Solution

MLFMA is not a standalone solver but an accelerator for iterative Krylov-subspace methods such as GMRES or BiCGSTAB applied to the method-of-moments (MoM) discretization of integral equations. At each iteration, the matrix-vector product is computed via MLFMA rather than explicit matrix multiplication. The book The Multilevel Fast Multipole Algorithm for Solving Large-Scale Computational Electromagnetics Problems by Ergul and Gurel provides a comprehensive reference for the integral equation formulations, preconditioner design, and parallel implementation strategies used in production MLFMA solvers.

Applications

MLFMA has applications in a range of engineering and scientific fields, including:

• Radar cross-section computation for aircraft, ships, and ground vehicles
• Antenna radiation pattern analysis for large phased arrays
• Electromagnetic compatibility and interference simulation
• Bioelectromagnetics, including scattering from human body models
• Optical scattering from metasurfaces and photonic structures
• Seismic and acoustic wave scattering in geophysics