Multilevel Fast Multipole Method (MLFMM)

Applicability of method

The EfieldFD MLFMM solver is suitable for analysis of very large problems where standard MoM are no longer applicable. Typical applications include

  • Radar cross section (RCS) analysis
  • Antenna integration on large structures
  • Reflector antenna design
  • Finite size antenna arrays
The MLFMM considerably reduces the solution time compared to MoM. In many cases the MLFMM is the only method available on the market that can solve these problems with sufficient accuracy.

Surface currents of reflector antenna Surface currents and monostatic RCS of UAV
Figure 1:  Reflector antenna (left) and UAV (right) computed with MLFMM


Description of method

The MLFMM is used to speed up matrix-vector multiplications which is 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 N3 and memory requirement is proportional to N2 . It is clear that using the MLFMM orders of magnitude are saved both in solution time and memory need.

MLFMM is based on 3D partition of the object into boxes as illustrated in Figure 1 and Figure 2. 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 are reduced significantly compared with MoM as is illustrated in Figure 3.

In Table 1. estimated memory requirements for the MLFMM and MoM are shown for some applications.

MLFMM partitioning of an aircraft
Figure 1:  MLFMM partitioning of an aircraft


MLFMM partitioning at different levels
Figure 2:  MLFMM partitioning at different levels


MoM (left) and two level MLFMM complexity (right)
Figure 3:  MoM (left) and two level MLFMM complexity (right)



Table 1. Estimated memory requirement for the MLFMM and MoM for some typical applications
Application and Frequency Number of unknowns MoM MLFMM
Satellite 1.5-2GHz 100000 150 Gb 1 Gb
Antenna installation at 1GHz Saab 2000 400000 2,4 Tb 4,5 Gb
RCS of military aircraft at 3 GHz 1 500 000 33,5 Tb 18 Gb


Solver features

Iterative Solvers

Solution of the matrix system is done using QMR or GMRES iterative solvers with a SPAI (Sparse Approximate Inverse) preconditioner to reduce the number of iterations.

Material and Boundary conditions

The EfieldFD MLFMM solver can handle lossy and lossfree dielectrics and magnetic materials, perfect electric and magnetic conductors as well as imprefectly conducting conductors. Boundary conditions that can be used are perfect electric and magnetic conductors (PEC/PMC) as well as imperfect conductors which are modeled using impedance boundary conditions (IBCs) or resistive boundary conditions (RBCs). Lumped elements (RLC) can be used on surface edges.

  • Dielectric and magnetic materials, lossy and lossfree
  • PEC
  • PMC
  • IBC
  • RBC
  • Lumped elements (RLC)

Excitations

Available excitations in the EfieldFD MLFMM solver are:

  • Plane wave
  • Dipole
  • Voltage excitations on surface edges
  • Waveguide mode excitations using 2D numerical or analytical eigenmode solver
  • General field distributions

Post-processing

Output from the EfieldFD MLFMM solver includes:

  • S-parameters
  • Input impedance
  • SVWR
  • Reflection loss
  • Far fields (2D, 3D, directivity, gain, field pattern, polarisation,...)
  • Radar Cross section (RCS) calculation, bistatic and monostatic
  • Near fields
  • Surface and wire currents
  • Far field power
  • Power through user defined surfaces

Parallelization and out-of-core

The MLFMM is fully parallelized for shared memory machines using OpenMP. For simulations including multiple right hand sides, such as for monostatic radar cross section analysis, the right hand sides can be specified to be stored on disc to reduce the use of main memory.

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.

RCS of small UAV Solution time for each right hand side
Figure 4:  Monostatic RCS of UAV (left) and solution time as function of monostatic direction with and without MRI (right)


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 is to compute the gain of large antennas as function of frequency or RCS computations as function of frequency.

Gain of horn antenna as function of frequency Solution time for each frequency
Figure 4:  Gain of circular horn antenna as function of frequency (left) and solution time as function of frequency number with and without MRI (right)


Integral equation formulations

In the EfieldFD MLFMM solver different integral formulations are available that improve 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
  • A new "CFIE" formulation based on a combination of PMCHWT and Muller formulations for problems involving both perfectly electric conductors and dielectric or magnetic bodies with outstanding convergence properties

Monostatic RCS of UAV with Radar Absorbing Material (RAM)

A new unique formulation for problems involving both perfectly electric conductors and dielectric or magnetic bodies with outstanding convergence properties were introduced in Efield® MLFMM version 5.0

  • RAM at leading edges
  • Improved integral equation formulation for mxed PEC and dielectric problems
  • Convergence study at 500 MHz
  • Comparison with standard PMCHWT formulation

UAV with RAM Convergence in MLFMM for UAV with RAM
Figure 4:  UAV with RAM