Fast Multipole Method for Large Structures

The fast multipole method (FMM) computational technique in Antenna Toolbox™ allows you to model and analyze antennas and arrays on large platforms like aircraft and automobiles.

Direct Solvers

The first step in the computational solution of electromagnetic problems is to discretize Maxwell's equations. The process results in this matrix-vector system:

$V = Z I$

V — Applied voltage vector. This signal can be voltage or power applied to the antenna or an incident signal falling on the antenna.
I — Current vector that represents current on the antenna surface.
Z — Interaction matrix or impedance matrix that relates V to I.

Antenna Toolbox uses Method of Moments Solver for Metal and Dielectric Structures to calculate the interaction matrix and solve system equations.

To calculate the surface currents on the antenna structure, you first define Rao-Wilton-Glisson (RWG) basis functions. A RWG basis function is a pair of triangles that share an edge, and is shown in the figure.

For any two triangle patches, $t_{n}^{+}$ and $t_{n}^{-}$ , having areas $A_{n}^{+}$ and $A_{n}^{-}$ , and sharing common edge $l_{n}$ , the basis function is

$\begin{array}{l} {\vec{f}}_{n} (\vec{r}) = {\begin{matrix} \frac{l_{n}}{2 A_{n}^{+}} {\vec{ρ}}_{n}^{+ S}, & \vec{r} \in t_{n}^{+} \\ \frac{l_{n}}{2 A_{n}^{-}} {\vec{ρ}}_{n}^{- S}, & \vec{r} \in t_{n}^{-} \end{matrix} \end{array}$

${\vec{ρ}}_{n}^{+} = \vec{r} - {\vec{r}}_{n}^{+}$ — Vector drawn from the free vertex of triangle $t_{n}^{+}$ to observation point $\vec{r}$
${\vec{ρ}}_{n}^{-} = {\vec{r}}_{n}^{+} - \vec{r}$ — Vector drawn from the observation point to the free vertex of the triangle $t_{n}^{-}$

and

$\nabla \cdot {\vec{f}}_{n} (\vec{r}) = {\begin{matrix} \frac{l_{n}}{A_{n}^{+}}, & \vec{r} \in t_{n}^{+} \\ - \frac{l_{n}}{A_{n}^{-}}, & \vec{r} \in t_{n}^{-} \end{matrix}$

The basis function is zero outside the two adjacent triangles $t_{n}^{+}$ and $t_{n}^{-}$ . The RWG vector basis function is linear and has no flux (no normal component) through its boundary.

Relation Between Memory Used and Problem Size

The interaction matrix Z is a complex dense symmetric matrix. It is a square N-by-N matrix, where N is the number of basis functions, that is, the number of interior edges in the structure. Consider the scenario of a large structure like an aircraft or a ship. Typical narrow-band antennas like the dipole or patch are half-wavelength in size, but ships or aircraft can often be at least 100 wavelengths or more in size. To solve for the electromagnetic effects of either radiation or scattering from this structure using a full-wave solver, the first step is to mesh the structure and then form the basis functions. Doing so generates more than 50,000 triangles. Since the memory requirement for the direct solver is of the order of O(N²), in basis function space, the growth is as shown in this plot.

Under any of the following conditions the number of the unknowns become very large:

High analysis frequency
Structure refined with a finer mesh
Analysis of a physically large structure

Fast Multipole Method (FMM)

The acceleration achieved by the FMM algorithm is due to its ability to subdivide the problem into successively smaller spatial regions, thereby ensuring that a given pair of source and target clusters are distant enough for the interaction to be computed using multipole expansions. The following figure illustrates that.

This approach fits well with the need to accelerate the computation of interactions between separated pairs of basis functions, that is, source and target dipole pairs. The problem of determining the electromagnetic potential at a given set of target points in a Helmholtz type of problem can be expressed as:

$u (r) = \sum_{n = 1}^{N} c_{n} \frac{\exp (j k | r - r_{n} |)}{| r - r_{n} |} - v_{n} \cdot \nabla (\frac{\exp (j k | r - r_{n} |)}{| r - r_{n} |})$

wherein, c_nand v_nrepresent the collection of charge and dipole strengths, respectively, k is the wavenumber, and u(r) is the potential computed by FMM in 3-D space.

FMM speeds up the computation of the matrix-vector product by substantially accelerating the computation of point-to-point interactions mediated by the Green's function. The original current and charge distributions on the surface of the target are determined by introducing these coefficients back into the basis function expansion. Scattered or radiated field of the target including its radar cross-sections is then found by computing the radiation of the known surface currents and charges at required points in space. The iterative approach to determining a matrix inverse is a well-studied and established field of applied linear algebra. Among the variety of iterative solvers that exist, the generalized minimum residual (GMRES) method is a well-known technique. Antenna Toolbox uses this iterative solver.

Electric Field Integral Equation (EFIE)

The direct solver implemented in the Antenna Toolbox is based on EFIE. EFIE uses the electric field relationships on the surface of a metal and at any point in free space to set up the system of equations.

$E_{t}^{s} = - E_{t}^{i}$

$E^{s} (r) = - j ω A - \nabla φ$

The index t in the first of the two equations is used to describe the tangential component of the electric field on a metal surface, index s describes the scattered field, and index i denotes the incident field. In the second equation the relationship of the scattered field is shown in terms of the electric scalar potential φ and magnetic vector potential A.

Applying the Galerkin approach, where the test using the basis functions leads to the following key equation:

$j ω {\frac{l_{m}}{2} p_{m}^{+} (r_{m}^{+}) \cdot A (r_{m}^{+}) + \frac{l_{m}}{2} p_{m}^{-} (r_{m}^{-}) \cdot A (r_{m}^{-})} - {l_{m} φ (r_{m}^{+}) - l_{m} φ (r_{m}^{-})} = V_{m}$

$V_{m} = \frac{l_{m}}{2} p_{m}^{+} (r_{m}^{+}) \cdot E^{i} (r_{m}^{+}) + \frac{l_{m}}{2} p_{m}^{-} (r_{m}^{-}) \cdot E^{i} (r_{m}^{-})$

Magnetic Field Integral Equation (MFIE)

MFIE equation expresses the surface current density J(r) developed on the body of a metallic object in response to a magnetic field excitation. An important observation here is that the second term of MFIE is the exact physical optics (PO) approximation. This equation captures the first order solution as the PO approximation, while the second term involving the integral captures the full-wave effects, thus providing a complete solution.

MFIE can be applied only to closed structures such as boxes, spheres, closed shells of aircraft, and so on. It cannot be applied, for example, to a strip dipole or monopole antenna.

$J (r) = 2 n (r) \times \int_{s} J (r') \times \nabla_{r'} \frac{\exp (- j k | r - r' |)}{4 π | r - r' |} d r' + 2 n (r) \times H^{i} (r)$

Using the collocation approach leads to the equation for the MFIE implementation:

$c_{m} - {I_{m} \cdot \sum_{n = 1}^{N_{f a c e t s}} (\begin{matrix} M_{1} \cdot \nabla \\ M_{2} \cdot \nabla \\ M_{3} \cdot \nabla \end{matrix}) \frac{\exp (- j k | R_{m} - r_{n} |)}{4 π | R_{m} - r_{n} |}} = I_{m}^{P O}$

$M_{1} = (\begin{matrix} 0 \\ - m_{z} \\ + m_{y} \end{matrix}), M_{2} = (\begin{matrix} + m_{z} \\ 0 \\ - m_{x} \end{matrix}), M_{3} = (\begin{matrix} - m_{y} \\ + m_{x} \\ 0 \end{matrix}), m = I_{n} r_{n}$

Combined Field Integral Equation (CFIE)

CFIE uses the two equations shown for EFIE and MFIE. The term α is chosen to be 0.5 and η = 376.3Ω is the free space impedance.

$α L H S E_{m} + (1 - α) η L H S H_{m} = α V_{m} + (1 - α) η I_{m}^{P O}$

The FMM solver is applied to compute the left side of this equation. LHSE_m represents the left side of EFIE and LHSH_m represents the left side of MFIE.

References

[1] Flatironinstitute/FMM3D. Fortran. 2018. Reprint, Flatiron Institute, 2021. https://github.com/flatironinstitute/FMM3D.

[2] Greengard, L, and V Rokhlin. “A Fast Algorithm for Particle Simulations.” Journal of Computational Physics 73, no. 2 (December 1987): 325–48. https://doi.org/10.1016/0021-9991(87)90140-9.

[3] Rius JM, Úbeda E, Parrón J. On The Testing of the Magnetic Field Integral Equation With RWG Basis Functions in Method of Moments. IEEE Trans. Antennas and Propagation, vol. AP-49, no. 11, pp. 1550-1553.

[4] Rao SM, Wilton DR, Glisson AW. Electromagnetic Scattering by Surfaces of Arbitrary Shape. IEEE Trans. on Antennas and Propagation. 1982 May;30(3):409-418. doi: 001 8-926X/82/0500-O409.