Personal tools
Sections

Multilevel Fast Multipole Method (MLFMM)

Multilevel Fast Multipole Method (MLFMM)
mlfmm_ac_boxes_small
MLFMM boxes at the 3rd finest level.

mlfmm_aggregate
Aggregation, translation and disaggregation.

General Applicability of the Technique

The MLFMM is an alternative formulation of the technology behind the MoM and is applicable to much larger structures than the MoM, making full-wave current-based solutions of electrically large structures a possibility. This fact implies that it can be applied to most large models that were previously treated with the MoM without having to change the mesh.

 

Technical Foundation

The agreement between the MoM and MLFMM is that basis functions model the interaction between all triangles. The MLFMM differs from the MoM in that it groups basis functions and computes the interaction between groups of basis functions, rather than between individual basis functions. FEKO employs a boxing algorithm that encloses the entire computational space in a single box at the highest level, dividing this box in 3 dimensions into a maximum of 8 child boxes and repeating the process iteratively until the side length of each child box is approximately a quarter wavelength at the lowest level. Only populated boxes are stored at each level, forming an efficient tree-like data structure. In the MoM framework the MLFMM is implemented though a process of aggregation, translation and disaggregation of the different levels.

The MoM treats each of the N basis functions in isolation, thus resulting in an N2 scaling of memory requirements (to store the impedance matrix) and N3 in CPU-time (to solve the linear set of equations). It is thus clear that processing requirements for MoM solutions scale rapidly with increasing problem size. The MLFMM formulation's more efficient treatment of the same problem results in N.log(N) scaling in memory and N.log(N).log(N) in CPU time. In real applications this reduction in solution requirements can range to orders of magnitude.

Significant effort has also been invested in improving the parallel MLFMM formulation to achieve exceptionally high efficiency when distributing a simulation over multiple processors. Here are some general memory estimates for different applications (specific cases may differ):

Application and Frequency Number of Unknowns Memory (MoM) Memory (MLFMM)
  • Military aircraft at 690 MHz
  • Ship (115m x 14 m) at 107 MHz
  • Reflector antenna with aperture size 19 lambda
100 000
150 GByte
1 GByte
  • Military aircraft at 1.37 GHz
  • Ship (115m x 14 m) at 214 MHz
  • Reflector antenna with aperture size 38 lambda
400 000
2.4 TByte
4.5 GByte
  • Military aircraft at 2.65 GHz
  • Ship (115m x 14 m) at 414 MHz
  • Reflector antenna with aperture size 73 lambda
1 500 000
33.5 TByte
18 GByte

 

Total run-time efficiency (all solution phases) for parallel MLFMM solution
of a problem with 3.18 million unknowns.

 

Simulating Complex Dielectric Objects in Large Metallic Structures

A weakness of the standard MLFMM formulation is that it is not well suited to the modelling of structures that contain complex dielectric elements.  FEKO overcomes this limitation by hybridisation of the MLFMM with the FEM method.  The FEM method is very well suited to the modelling of complex dielectric objects.  The FEM can be used to model complex dielectric areas in the presence of large platforms, while the MLFMM is still used for the optimal solution of the large platforms.

Examples of problems that can be solved with this approach include:

  • Placing a complex microstrip antenna with finite sized dielectric on an aircraft, ship or land vehicle for investigation of antenna placement problems.
  • Placing phantoms (models of humans) inside vehicles, or in close proximity to large platforms with radiating elements for the investigation of possible hazardous radiation conditions, e.g. computing SAR levels.

 

farfield_3D_surfaces.png

FEM/MLFMM analysis of a transmitting antenna on a vehicle (MLFMM solution)
with four human passengers (FEM solution) inside.

Simulation of Very Large Electric Structures in Hybridisation with PO

Despite the MLFMM's efficiency at full wave solution of electrically large structures, some problems may still present themselves where the MLFMM may require more resources than is on offer by the host computer.  FEKO overcomes this stumbling block by hybridisation of the MLFMM with the PO and LE-PO methods.  The PO or LE-PO methods may then be used to solve appropriate areas of the model in an asymptotic fashion, while the MLFMM is applied to areas where full wave modelling remains important.

Examples of problems that can be solved with this approach include:

  • Cassegrain or similar antennas where a very large main reflector is combined with a sub-reflector and feed horn.  The main reflector may solved very efficiently and accurately with the PO or LE-PO methods, while the MLFMM is applied to the sub-reflector and horn antenna combination.
  • Antenna placement on large platforms at very high frequencies.  The antenna (possibly geometrically complex) or multiple antennas maybe treated with the MLFMM, while the rest of the platform is solved with the PO.

 

MLFMM-LE-PO-hybrid.jpg

MLFMM/LE-PO analysis of a large Gregorian antenna

 

Typical Application of the MLFMM

Possible applications of the MLFMM span a wide range of problems. It is best suited to problems that include electrically large structures, e.g. antenna coupling on ships, antenna placement on aircraft and radiation hazard analysis behind a reflector antenna.  The MLFMM is a very efficient solution for full-wave RCS computation and employs smart initialization methods to speed up convergence for monostatic RCS simulations.

 

mlfmm_ship_small MLFMM_antennaplacement_smaller
MLFMM analysis of a ship. Antenna placement on a commercial aircraft.
Additional Information

Additional Information