# Multilevel Fast Multipole Method (MLFMM)

For applications involving electrically large structures such as antenna installation analysis, radar cross section analysis or reflector antenna design the MLFMM approach can be used to reduce the numerical complexity. In many cases the MLFMM is the only method available on the market that can solve these problems with sufficient accuracy.

## Description of method

The MLFMM is used to speed up matrix-vector multiplications which are the dominating operation in the iterative solver used in the EfieldFD MLFMM solver to solve the MoM matrix system. When using a MLFMM technique the solution time is proportional to Niter N log(N) and the memory requirement is proportional to N log(N), where N is the number of unknowns in the matrix system and Niter is the number of iterations in the iterative solver. This should be compared to MoM where solution time is proportional to N^{3} and memory requirement is proportional to N^{2}. It is clear that by using MLFMM orders of magnitude are saved both in solution time and memory need.

MLFMM is based on 3D partition of the object into boxes. The object is placed in a box which is split in 8 smaller boxes. Each of the boxes are then divided again recursively until the size of the smallest box only contains a few basis functions. Non-empty boxes are not stored so the tree structure is sparse.

Using the MLFMM partition of the object into boxes of different size at different levels a fast matrix-vector multiplication can be computed. The near field interactions are calculated at once by standard MoM. The far-field interactions are calculated iteratively by traversing the tree structure (upward and downward pass) and use an operator to translate radiated fields at the box centers into incoming fields for the other boxes. Using the MLFMM the complexity in the matrix-vector multiplication is reduced significantly compared with MoM.

## Solver features

### Fast Monostatic RCS computation using MRI

The MLFMM solver use the MRI (Minimal Residual Interpolation) method that reduces the number of iterations in the iterative MLFMM solver for multiple right hand sides such as in case of monostatic RCS computations. The MRI method computes an optimal initial guess of the solution of a particular right hand side used by the iterative solver. The initial guess is based on previously computed solutions and is optimal in the sense that the residual of the initial guess is minimized. Given an optimal initial guess the number of iterations in the iterative MLFMM solver is drastically reduced with great savings in solution time. After a certain number of solutions have been computed the remaining solutions can be computed by pure interpolation.

### Fast Frequency Sweep using MRI

The MRI method used for monostatic RCS computations are also used to speed up frequency sweeps with large savings in solution time. Typical applications are to compute the gain of large antennas as function of frequency or RCS computations as function of frequency.

### Integral equation formulations

In the EfieldFD MLFMM solver different integral formulations are available that improves accuracy and decrease solution time. Available formulations include EFIE, MFIE and CFIE for perfectly electric conductors, PMCHWT (Poggio-Miller-Chang-Harrington-Wu-Tsai) formulation for problems involving both perfectly electric conductors and dielectric or magnetic bodies. There is also a new CFIE based formulation combining PMCHWT and Muller formulations for problems involving both perfectly electric conductors and dielectric or magnetic bodies with outstanding convergence properties.