# The MLFMA Equipped with a Hybrid Tree Structure for the Multiscale EM Scattering

Authors: Wei-Bin Kong; Hou-Xing Zhou; Wei-Dong Li; Guang Hua; Wei Hong
Journal: International Journal of Antennas and Propagation
 (2014)

---

## Abstract

We present an efficient strategy for reducing the memory requirement for the near-field matrix in the multilevel fast multipole algorithm (MLFMA) for solving multiscale electromagnetic (EM) scattering problems. A multiscale problem can obviously lower the storage efficiency of the MLFMA for the near-field matrix. This paper focuses on overcoming this shortcoming to a certain extent. A hybrid tree structure for the MLFMA that possesses two kinds of bottom-layer boxes with different edge sizes will be built to significantly reduce the memory requirement for the near-field matrix in the multiscale case compared with the single-tree-structure technique. Several numerical examples are provided to demonstrate the efficiency of the proposed scheme in the multiscale EM scattering.


---

## Body

## 1. Introduction

The method of moments (MoM) [1] has been widely used due to its superior capability to handle arbitrarily shaped objects in electromagnetic (EM) radiation and scattering problems. The computational complexity of the MoM is O
(
N
3
) for a direct solver like the LU and O
(
m
N
2
) for an iterative solver like the CG, where N is the number of unknowns and m is the iteration count.Because of its higher complexity, the traditional MoM is not suitable for solving electrically large EM problems. The multilevel fast multipole algorithm (MLFMA) [2–4] can reduce the computational complexity of a matrix-vector product from O
(
N
2
) to O
(
N
log
⁡
⁡
N
) as well as the storage complexity of the MoM matrix from O
(
N
2
) to O
(
N
). Such an advancement thanks to the application of the addition theorem of the Green’s function and the introduction of the octree structure. To further improve the computational efficiency, the MLFMA can be combined with parallel computing technology [5–11].In EM simulation, the Rao-Wilton-Glisson (RWG) basis functions [12] are frequently selected to build a MLFMA model for an electrically large object. For this, the surface of the electrically large object is generally discretized with about 10 elements per wavelength. In such a case, the octree whose bottom-layer or finest-layer boxes have edge size of about 0.3 wavelength is more suitable for grouping all basis functions. However, a multiscale problem can obviously lower the storage efficiency of the MLFMA for the near-field matrix, because some local regions of the object surface need to be overmeshed to capture tiny geometry features, leading to a very large near-field matrix if the single octree structure is still used. In order to take care of the fine mesh parts, smaller bottom-layer boxes seem to be considered. However, the bottom-layer boxes with edge size of 0.15 wavelength are not suitable for grouping those RWG basis functions with edge size of about 0.1 wavelength. Besides, the box edge size of 0.15 wavelength is already very close to the subwavelength breakdown of the MLFMA (or the HF-MLFMA) [13–19]. Introducing some assistive technology can alleviate this problem to a certain extent. In [20], Pan et al. combined the interpolative decomposition (ID) with the MLFMA to alleviate the multiscale problem. In [21], Vikram et al. combined the accelerated Cartesian expansion (ACE) with the MLFMA to alleviate the multiscale problem.In this paper, we focus on overcoming the multiscale problem to a certain extent. A hybrid tree structure for the MLFMA that possesses two kinds of bottom-layer boxes with different edge sizes will be built to significantly reduce the memory requirement for the near-field matrix in the multiscale case compared with the single-tree-structure technique. Compared with the previous methods [20, 21], this method is particularly simple and easy to implement. The idea of this method germinated in our previous work [22]. Several numerical examples are provided to demonstrate the efficiency of the proposed method in the multiscale EM scattering.This paper is organized as follows. In Section2, the hybrid tree structure (HTS) is built. In Section 3, the MLFMA equipped with a HTS is presented. In Section 4, numerical examples are provided. Finally, the conclusion is given in Section 5. Besides, in this paper, λ always denotes the wavelength in the free space.


## 2. The Hybrid Tree Structure

In the EM simulation using the RWG basis functions, the surface of an electrically large perfectly conducting object is discretized with more than or equal to 10 elements per wavelength. To build a MLFMA model, an octree structure for grouping all basis functions must be constructed. For this, the entire object is enclosed within a large box, called 0-layer box. Then the 0-layer box is divided into its eight children boxes, called 1-layer boxes. Each 1-layer box is divided into its eight children boxes, called 2-layer boxes, until the edge size of the finest-layer boxes is about 0.3 wavelength [2–4]. All basis functions are grouped into the corresponding finest-layer or bottom-layer boxes. Only the nonempty boxes are retained at all levels. In this way, we build a hierarchy of the boxes for the entire object.The MLFMA splits a matrix-vector product into two parts: near-field interactions and far-field interactions. The near-field interactions between adjacent boxes at the bottom layer form the near-field matrix of the MLFMA. Now, the edge size of the bottom-layer boxes is selected to be0.3
λ. At this time, the number of the RWG basis functions with edge size of about 0.1
λ in a bottom-layer box is usually less than 50. However, if some local regions of the object are overmeshed, for example, if the discrete sizes are less than or equal to 0.05
λ, then the numbers of the RWG basis functions in some bottom-layer boxes can exceed 100. This is why a multiscale problem can lead to a very large near-field matrix. Thus, it is a meaningful work to build a proper tree structure for the MLFMA in the multiscale case.As elucidated in [18], in most cases, the numerical error produced by 0.2
λ bottom-layer-box size is acceptable. If the box size is below 0.2
λ, the MLFMA could suffer from subwavelength breakdown [13–19]. Hence, 0.2
λ is an appropriate choice for the bottom-layer-box size when the discrete sizes of some local regions are less than or equal to 0.05
λ. According to the different surface discretization, a hybrid of the octree structure and the 27-tree structure will be a better choice for the MLFMA in the multiscale case. In such a hybrid tree structure, there are two kinds of bottom-layer boxes. One has the edge size of 0.3 wavelength and another has the edge size of 0.2 wavelength, as shown in Figure 1.Figure 1
Two kinds of the bottom-layer boxes. For example, each purple or black box is a bottom-layer box in the octree structure, while each blue box is a bottom-layer box in the 27-tree structure.The formation process of the HTS is closely related to the surface discretization and difficult to be described with a few formulas, but this process is very easy for a computer language to describe. Here, our purpose is just to show how a hybrid tree structure is applied in the MLFMA. Then, the situation in Figure1 can be used as a simple example. In this case, the formation procedure can be outlined as follows.(1)
The entire object is enclosed within a large box, called 0-layer box.
(2)
Then the 0-layer box is divided into its eight children boxes, called 1-layer boxes. Each 1-layer box is divided into its eight children boxes, called 2-layer boxes, until the edge size of the bottom-layer boxes is about0.3
λ.
(3)
Group all basis functions into the corresponding current bottom-layer boxes and record the number of the basis functions in each current bottom-layer box.
(4)
If one bottom-layer box contains more than50 basis functions, then mark its parent box. Redivide this parent box marked into 27 children boxes with edge size of 0.2
λ.
(5)
After the process described by(
4
) for all bottom-layer boxes is finished, some basis functions have temporarily lost the bottom-layer boxes containing them. Regroup these basis functions into the corresponding new bottom-layer boxes whose edge size is 0.2
λ.In this way, we build a hierarchy of boxes for all basis functions. Clearly, the finest layer in the above hybrid tree structure is an imprecise concept. In fact, there are two kinds of the bottom-layer edge sizes, that is,0.3
λ and 0.2
λ. Figure 2 shows such a tree structure for the MLFMA.Figure 2
The hybrid tree structure in the 2D case.


## 3. The MLFMA Equipped with a HTS

Two boxes at the same layer are called near-neighbours if they have at least one common point. In the following, all boxes mentioned are not empty. For convenience, we also need some notations.Definition 1.
Let “ob” be an observed box; thenN
n
(
ob
) is a collection that consists of “ob” and all its near-neighbours. Here, the subscript n in N
n
(
ob
) means “near-neighbours.”Definition 2.
Let “ob” be an observed box; thenN
n
n
(
ob
) is a collection that consists of those children of all near-neighbours of ob parent box that are well separated from ob. Here, the subscript n
n in N
n
n
(
ob
) means “next near-neighbours.” Figure 3 shows the members of N
n
(
ob
) and N
n
n
(
ob
) related to a bottom-layer box ob in the HTS.Figure 3
An observed box (ob) at the bottom layer and all its near-neighbours (nb) and all next near-neighbours (nnb).As usual, the near-field matrix formed by the interactions between the near-neighbours at the bottom layer is directly calculated and stored in advance. The product of the near-field matrix with a vector is always directly calculated.Assume that the RWG functionsJ
⃑
i and J
⃑
j belong to the next near-neighbours B
m and B
n, respectively. The location vectors of the centers of B
m and B
n are denoted by r
⃑
m and r
⃑
n, respectively. The location vectors of any points on supports of J
⃑
i and J
⃑
j are denoted by r
⃑
i and r
⃑
j, respectively. Furthermore, define r
⃑
i
m
=
r
⃑
i
-
r
⃑
m, r
⃑
n
j
=
r
⃑
n
-
r
⃑
j, and r
⃑
m
n
=
r
⃑
m
-
r
⃑
n. Then, the far-matrix elements formed by the interactions between these two next near-neighbours for the combined field integral equation (CFIE) are expressed as
(1)
Z
i
j
C
=
∫
Ω
‍
d
2
k
^
V
⃑
f
i
m
(
k
^
)
·
α
m
n
(
k
^
)
·
V
⃑
s
n
j
(
k
^
)
,
where
(2)
V
⃑
f
i
m
(
k
^
)
=
γ
∫
S
i
‍
[
I
̿
-
k
^
k
^
]
·
J
⃑
i
(
r
⃑
i
m
)
e
-
j
k
⃑
·
r
⃑
i
m
d
s
+
(
1
-
γ
)
∫
S
i
‍
[
J
⃑
i
(
r
⃑
i
m
)
×
n
^
]
×
k
^
e
-
j
k
⃑
·
r
⃑
i
m
d
s
,
V
⃑
s
n
j
(
k
^
)
=
∫
S
j
‍
[
I
̿
-
k
^
k
^
]
·
J
⃑
j
(
r
⃑
n
j
)
e
-
j
k
⃑
·
r
⃑
n
j
d
s
,
(3)
α
m
n
(
k
^
)
=
j
η
0
2
T
L
(
k
⃑
,
r
⃑
m
n
)
,
where γ is the combination factor and 0
≤
γ
≤
1. In this paper, γ is selected to be 0.5.The formula (1) can be decomposed into three processes: the aggregation process, the translation process, and the disaggregation process. For the sake of clarity, an example in Figure 4 is considered. Compared with the conventional MLFMA, the MLFMA equipped with a HTS contains more details about the aggregation, translation, and disaggregation at the bottom layer.Figure 4
The process of aggregation, translation, and disaggregation, where each “•” represents the center of a bottom-layer box.In Figure4, the solid purple arrow line illustrates the aggregation, translation, and disaggregation processes between two next near-neighbours at the bottom layer of different sizes, whose centers are marked with r
⃑
m and r
⃑
n, respectively. There is an indirect transmission of information between two basis functions marked with r
⃑
i and r
⃑
j, respectively. That is, r
⃑
j
→
r
⃑
n
→
r
⃑
m
→
r
⃑
i. Two solid black arrow lines illustrate the aggregation, translation, and disaggregation processes between two next near-neighbours at the bottom layer of the same sizes. It should be noted that the higher layer calculation is the same as the conventional MLFMA.


## 4. Numerical Examples

In this section, the conductor surface is meshed with triangular elements and RWG functions [12] are chosen as both basis and test functions, where the edge sizes of the triangular elements are from 0.05
λ to 0.1
λ. The singularity of the near-field matrix elements is dealt with through the approach in [23].


### 4.1. A PEC Sphere with Radius 2.0λ

A perfectly electric conducting (PEC) sphere with radius size2.0
λ is considered in Figure 5. The upper hemisphere surface is discretized with edge size of about 0.05
λ, and the lower hemisphere surface is discretized with edge size of about 0.1
λ, producing 47148 unknowns.Figure 5
Mesh of a PEC sphere with radius2
λ.Figure6 depicts the bistatic RCS curves obtained by the Mie solution [24], the conventional MLFMA, and the MLFMA equipped with a HTS. The numbers of the bottom-layer boxes in the conventional MLFMA and the MLFMA equipped with a HTS are 784 and 1273, respectively, as shown in Table 1. The memory requirement for both the fast methods is 896.796 MB and 450.876 MB, respectively, and hence the new method leads to 50.28% memory reduction.Table 1
Comparison between the two MLFMAs in Section4.1.
MLFMA
MLFMA equipped with a HTS
Number of levels
4
4
Number of bottom-layer boxes
784
1273
Memory for the near-field matrix
896.796 MB
450.876 MBFigure 6
Bistatic RCS curves of the PEC sphere.


### 4.2. A PEC Rectangular Plate with Thin Slots

Next, we consider the EM scattering from a PEC rectangular plate with thin slots, as shown in Figure7. The plate surface is discretized into a lot of triangles, yielding 15153 unknowns. Because there are tiny geometric details, the resulting mesh is a multiscale mesh and also an extremely nonuniform mesh. The longest edge size is about 0.1
λ, while the shortest edge size is about 0.05
λ.Figure 7
Mesh of a PEC rectangular plate with thin slots. The dimension of the plate is8
λ by 4
λ and that of each slot is 4
λ by 0.05
λ.Figure8 depicts the bistatic RCS curves obtained by the MoM, the conventional MLFMA, and the MLFMA equipped with a HTS. The numbers of the bottom-layer boxes in the conventional MLFMA and in the MLFMA equipped with a HTS are 378 and 473, respectively, as shown in Table 2. The memory requirement for both the fast methods is 104.76 MB and 81.85 MB, respectively, and hence the new method leads to 21.9% memory reduction.Table 2
Comparison between the two MLFMAs in Section4.2.
MLFMA
MLFMA equipped with a HTS
Number of levels
6
6
Number of bottom-layer boxes
378
473
Memory for the near-field matrix
104.76 MB
81.85 MBFigure 8
Bistatic RCS curves of the PEC plate with thin slots.


### 4.3. A PEC Aircraft-Like Model

The last structure is a PEC aircraft-like model in Figure9. The width is 13
λ and the length is 18.5
λ. The head part of flyer is discretized with edge size of about 0.05
λ, and the remaining part is discretized with edge size of about 0.1
λ. The number of unknowns is 54159.Figure 9
Mesh of the PEC aircraft-like model.In Figure10, the bistatic RCS results are plotted, which is obtained by the conventional MLFMA and the MLFMA equipped with a HTS. The numbers of the bottom-layer boxes in the conventional MLFMA and the MLFMA equipped with a HTS are 1793 and 1902, respectively, as shown in Table 3. The memory requirement for both the fast methods is 494.83 MB and 409.97 MB, respectively, and hence the new method leads to 17.15% memory reduction.Table 3
Comparison between the two MLFMAs in Section4.3.
MLFMA
MLFMA equipped with a HTS
Number of levels
7
7
Number of the bottom-layer boxes
1793
1902
Memory for the near-field matrix
494.83 MB
409.97 MBFigure 10
Bistatic RCS curves of the PEC aircraft-like model.


## 4.1. A PEC Sphere with Radius 2.0λ

A perfectly electric conducting (PEC) sphere with radius size2.0
λ is considered in Figure 5. The upper hemisphere surface is discretized with edge size of about 0.05
λ, and the lower hemisphere surface is discretized with edge size of about 0.1
λ, producing 47148 unknowns.Figure 5
Mesh of a PEC sphere with radius2
λ.Figure6 depicts the bistatic RCS curves obtained by the Mie solution [24], the conventional MLFMA, and the MLFMA equipped with a HTS. The numbers of the bottom-layer boxes in the conventional MLFMA and the MLFMA equipped with a HTS are 784 and 1273, respectively, as shown in Table 1. The memory requirement for both the fast methods is 896.796 MB and 450.876 MB, respectively, and hence the new method leads to 50.28% memory reduction.Table 1
Comparison between the two MLFMAs in Section4.1.
MLFMA
MLFMA equipped with a HTS
Number of levels
4
4
Number of bottom-layer boxes
784
1273
Memory for the near-field matrix
896.796 MB
450.876 MBFigure 6
Bistatic RCS curves of the PEC sphere.


## 4.2. A PEC Rectangular Plate with Thin Slots

Next, we consider the EM scattering from a PEC rectangular plate with thin slots, as shown in Figure7. The plate surface is discretized into a lot of triangles, yielding 15153 unknowns. Because there are tiny geometric details, the resulting mesh is a multiscale mesh and also an extremely nonuniform mesh. The longest edge size is about 0.1
λ, while the shortest edge size is about 0.05
λ.Figure 7
Mesh of a PEC rectangular plate with thin slots. The dimension of the plate is8
λ by 4
λ and that of each slot is 4
λ by 0.05
λ.Figure8 depicts the bistatic RCS curves obtained by the MoM, the conventional MLFMA, and the MLFMA equipped with a HTS. The numbers of the bottom-layer boxes in the conventional MLFMA and in the MLFMA equipped with a HTS are 378 and 473, respectively, as shown in Table 2. The memory requirement for both the fast methods is 104.76 MB and 81.85 MB, respectively, and hence the new method leads to 21.9% memory reduction.Table 2
Comparison between the two MLFMAs in Section4.2.
MLFMA
MLFMA equipped with a HTS
Number of levels
6
6
Number of bottom-layer boxes
378
473
Memory for the near-field matrix
104.76 MB
81.85 MBFigure 8
Bistatic RCS curves of the PEC plate with thin slots.


## 4.3. A PEC Aircraft-Like Model

The last structure is a PEC aircraft-like model in Figure9. The width is 13
λ and the length is 18.5
λ. The head part of flyer is discretized with edge size of about 0.05
λ, and the remaining part is discretized with edge size of about 0.1
λ. The number of unknowns is 54159.Figure 9
Mesh of the PEC aircraft-like model.In Figure10, the bistatic RCS results are plotted, which is obtained by the conventional MLFMA and the MLFMA equipped with a HTS. The numbers of the bottom-layer boxes in the conventional MLFMA and the MLFMA equipped with a HTS are 1793 and 1902, respectively, as shown in Table 3. The memory requirement for both the fast methods is 494.83 MB and 409.97 MB, respectively, and hence the new method leads to 17.15% memory reduction.Table 3
Comparison between the two MLFMAs in Section4.3.
MLFMA
MLFMA equipped with a HTS
Number of levels
7
7
Number of the bottom-layer boxes
1793
1902
Memory for the near-field matrix
494.83 MB
409.97 MBFigure 10
Bistatic RCS curves of the PEC aircraft-like model.


## 5. Conclusions

In the multiscale case, a single octree structure for the MLFMA can produce a very large near-field matrix. In this paper, in order to overcome this shortcoming to a certain extent, a hybrid tree structure scheme has been established. In this scheme, there are two kinds of bottom-layer boxes with different edge sizes. With the hybrid tree structure, the memory requirement for the near-field matrix can be significantly reduced in the multiscale case compared with the MLFMA equipped with a single octree structure.It should be pointed out that to what extent the total amount of storage is reduced by the proposed method is closely related to the proportion of the local regions with the tiny geometry features to the whole surface domain. This fact has been revealed by the three numerical examples provided in this paper. Therefore, in the general case, to what exact extent the proposed method can reduce the total amount of storage can not be determined in advance.



---

*Source: 281303-2014-02-19.xml*