# Application of Hierarchical Two-Level Spectral Preconditioning Method for Electromagnetic Scattering from the Rough Surface

Authors: D. Z. Ding; G. M. Li; Y. Y. An; R. S. Chen
Journal: International Journal of Antennas and Propagation
 (2014)

---

## Abstract

The higher-order hierarchical Legendre basis functions combining the electrical field integral equations (EFIE) are developed to solve the scattering problems from the rough surface. The hierarchical two-level spectral preconditioning method is developed for the generalized minimal residual iterative method (GMRES). The hierarchical two-level spectral preconditioner is constructed by combining the spectral preconditioner and sparse approximate inverse (SAI) preconditioner to speed up the convergence rate of iterative methods. The multilevel fast multipole method (MLFMM) is employed to reduce memory requirement and computational complexity of the method of moments (MoM) solution. The accuracy and efficiency are confirmed with a couple of numerical examples.


---

## Body

## 1. Introduction

The study of electromagnetic scattering from an object above a rough surface has a large number of applications, for example, in remote sensing, radar surveillance, and so on [1–14]. Consequently, accurate and efficient investigation of the composite scattering problem is an important subject in computational electromagnetics and remote sensing society. Both the approximate and rigorous methods have been developed to tackle this problem. Among the approximate methods, some are based on small perturbation method (SPM) [12], Kirchhoff approximation (KA) [13], small slope approximation (SSA) [14] and so on. However, the height value must be very small compared to the electromagnetic wave length in the SPM, the radius of the surface must be larger than a wavelength in the KA, the slope must be small and the height must be moderate for the first order in the SSA.For rigorous methods, the method of moments (MoM) [15–19] is one of the most widespread and generally accepted techniques for analyzing rough surface scattering. In MoM, the RWG functions [18] are often used for representing unknown current distributions due to the fact that it is convenient to model objects with arbitrary shape using triangular patches. When iterative solvers are used to solve the MoM matrix equation, the fast multipole method (FMM) or multilevel fast multipole method (MLFMM) [16, 17] can be used to accelerate the calculation of matrix-vector multiplies.For large rough surfaces, the RWG functions have a poor convergence and need a large number of unknowns for a desired accuracy. To circumvent this disadvantage, a remedy is to employ higher order basis functions [19–25]. The high order functions can be categorized as interpolatory or hierarchical. The Hierarchical functions allow for much greater flexibility [22–25]. The basis of order M is a subset of the basis of order M
+
1, which allows mixing of different order bases in the same mesh. Andersen and Volakis proposed a class of hierarchical tangential vector finite elements (TVFE’s) for FEM discretization [22]. Webb also introduced a set of hierarchical vector basis functions of arbitrary order for triangular and tetrahedral finite elements [23]. Jorgensen et al. proposed a new set of higher order hierarchical Legendre basis functions for a quadrilaterals element for integral equations solved with MoM [24]. The higher order hierarchical Legendre basis functions can preserve almost perfect orthogonality while enforcing continuity of the normal current component across surface element, which can provide a much better condition number of the MoM matrix than other higher order hierarchical basis functions and can remarkably reduce the computational costs compared with the RWG basis function. Yang et al. successfully used higher order hierarchical Legendre basis functions to analyze the electromagnetic scattering from breaking waves at low grazing angles [25].The system matrix in MoM from the divergence-conforming higher order basis functions is often an ill-conditioned matrix and result in the low convergence of the Krylov iterative method. Simple preconditioners like the Diagonal preconditioner (Diag) or symmetrical successive over-relaxation preconditioner (SSOR) can be effective only when the matrix has some degree of diagonal dominance [26]. Incomplete LU (ILU) preconditioners have been successfully used on nonsysmmetric dense systems in [27, 28]. Pan and Sheng also developed the multilevel inverse-based ILU preconditioning technique based on MLFMA for effectively analysis of electromagnetic scattering from complex targets [29]. However, the factors of the ILU preconditioner may become very ill-conditioned, and consequently the performance is very poor. An effective SAI preconditioner suitable for implementation in the FMM context has also been proposed [30], which is based on a Frobenius-norm minimization with a priori sparsity pattern selection strategy. Malas and Gürel proposed an efficient parallel SAI preconditioner combined with MLFMA in [31]. Fan et al. proposed the preconditioning matrix interpolation technique for the fast analysis of the radar cross-section (RCS) over a broad frequency band [32]. In [32], both the near field impedance and SAI preconditioning matrices are interpolated at intermediate frequencies over a relatively large frequency band with rational function interpolation technique.Although the SAI preconditioner can improve matrix conditions by clustering most of the large eigenvalues close to one but still leave a few close to the origin, which can potentially slow down the convergence of Krylov methods. Inherited from the basic idea of the traditional two-grid cycle of the multigrid methods [33, 34], the high frequency components of the iteration error belong to the subspace spanned by the eigenvectors associated with the large eigenvalues of the system matrix and can be represented on a fine grid defined by the higher order basis functions. The low frequency components left in the error are smooth enough and then can be represented on a coarse grid defined by the lower order basis functions.In this paper, we apply similar ideas to improve the quality of a prescribed SAI preconditioner based on the higher order hierarchical basis functions. Due to the property of the hierarchical basis functions, the hierarchical two-level spectral preconditioning method is used to accelerate the convergence of the iterative method [35]. In this method, the SAI preconditioner based on the higher order hierarchical basis functions is used to damp the high frequencies of the error, while the spectral preconditioner [36] in a two-level manner based on the lower order hierarchical basis functions is applied to smooth the low frequencies of the error.The goal of this paper is to achieve accurate and fast analysis of the electromagnetic wave scattering from a rough surface. The remainder of this paper is organized as follows. In Section2, theory and formulations are discussed. Numerical results are presented in Section 3 to demonstrate the accuracy and efficiency of the presented method. Section 4 concludes this paper. The time factor e
-
i
ω
t is assumed and suppressed throughout this paper.


## 2. Theory and Formulation

### 2.1. Rough Surface Modeling and EFIE

As shown in Figure1, a perfectly electric conductor (PEC) cubic is located above a PEC rough surface. The rough surface is a Gaussian stationary stochastic process with a zero mean value, which can easily be generated by a spectral method. In order to eliminate the edge effects caused by truncation of the finite surface length, the tapered wave is usually employed [1]. A TE-polarized tapered wave can be expressed as
(1)
E
→
i
(
r
→
)
=
exp
⁡
[
-
i
k
(
z
cos
⁡
θ
i
+
x
sin
θ
i
cos
⁡
ϕ
i
+
y
sin
θ
i
sin
ϕ
i
)
h
h
h
h
h
h
×
(
1
+
w
)
(
z
cos
⁡
θ
i
+
x
sin
θ
i
cos
⁡
ϕ
i
+
y
sin
θ
i
sin
ϕ
i
)

]
×
exp
⁡
(
-
t
x
-
t
y
)
,
t
x
=
(
x
cos
⁡
θ
i
cos
⁡
ϕ
i
+
y
cos
⁡
θ
i
sin
ϕ
i
+
z
sin
θ
i
)
2
g
2
cos
⁡
θ
i
2
t
y
=
(
-
x
sin
ϕ
i
+
y
cos
⁡
ϕ
i
)
2
g
2
w
=
1
k
2
(
2
t
x
-
1
g
2
cos
⁡
2
θ
i
+
2
t
y
-
1
g
2
)
,
where g is the widith of the tapered wave, θ
i and ϕ
i are elevation angle and azimuth angle of the incident wave, respectively. L is truncated length of rough surface. The width of the tapered wave should be large enough to illuminate upon the surface [2, 5].Figure 1
Geometric model of EM scattering from the rough surface.When there is no object above the PEC rough surface, the induced currentJ
r
′
→
(
r
→
) on the rough surface is
(2)
J
r
′
→
(
r
→
)
=
2
n
^
×
H
→
i
(
r
→
)
,
where H
→
i
(
r
→
) denotes the incident magnetic field. When there is no object above the rough surface, the scattering field E
→
s
r
(
r
→
) above the rough surface can be written as
(3)
E
→
s
r
(
r
→
)
=
i
ω
μ
∫
S
2
G
→
→
0
(
r
→
,
r
→
′
)
·
J
r
′
→
(
r
→
)
d
S
′
,
where r
→ is the position point on the rough surface S
2 and r
→
′ is observation point. G
→
→
0
(
r
→
,
r
→
′
) is dyadic free space Green’s function
(4)
G
→
→
0
(
r
→
,
r
→
′
)
=
[
I
̿
-
1
k
2
∇
∇
′
]
e
i
k
|
r
→
-
r
→
′
|
|
r
→
-
r
→
′
|
.
When the object exists above the PEC rough surface, the scattering field E
→
s
o
(
r
→
) above the rough surface can be written as
(5)
E
→
s
o
(
r
→
)
=
∫
S
1
G
→
→
e
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
,
where J
→
o
(
r
→
) is the induced current on the surface S
1 of object, G
→
→
e
(
r
→
,
r
→
′
) denotes the dyadic Green’s function in rough surface [37] as the following:
(6)
G
→
→
e
(
r
→
,
r
→
′
)
=
i
ω
μ
{
∫
S
2
G
→
→
0
(
r
→
,
r
′′
→
)
·
{
2
n
^
×
[
∇
g
(
r
′′
→
,
r
′
→
)
×
I
-
-
]
}
d
s
′
′
G
→
→
0
(
r
→
,
r
→
′
)
h
h
h
h
h
h
h
h
h
+
∫
S
2
G
→
→
0
(
r
→
,
r
→
′′
)
·
{
2
n
^
×
[
∇
g
(
r
→
′′
,
r
→
′
)
×
I
-
-
]
}
d
s
′
′
}
.
Substituting G
→
→
e
(
r
→
,
r
→
′
) into (5) gives
(7)
E
→
s
o
(
r
→
)
=
∫
S
1
G
→
→
e
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
=
i
ω
μ
∫
S
1
G
→
→
0
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
+
i
ω
μ
∫
S
1
G
→
→
s
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
(8)
G
→
→
s
(
r
→
,
r
→
′
)
=
∫
S
2
G
→
→
0
(
r
→
,
r
→
′′
)
·
{
2
n
^
×
[
∇
g
(
r
→
′′
,
r
→
′
)
×
I
→
→
]
}
d
s
′′
.
The first term at the right side of (7) represents the scattering field without object above the rough surface, the second term represents the coupling interactions between the rough surface and the object.


### 2.2. Higher Order Hierarchical Legendre Basis Functions

Equations (7) can be solved by MoM. The factor that most limits the capability of the MoM is the number of unknowns. As was pointed out in the introduction, this limitation can be relaxed by using higher order basis functions. For a given accuracy, the use of higher order basis functions allows us to use larger triangular patches to discrete the objects. In this paper, higher order hierarchical Legendre basis Functions defined on curvilinear quadrilateral surface [24, 25] are chosen to represent the surface current J
→
o as
(9)
J
→
o
=
J
S
u
a
→
u
+
J
S
v
a
→
v
,
where a
→
u and a
→
v are the co-variant unitary vectors as a
→
u
=
∂
r
→
/
∂
u and a
→
v
=
∂
r
→
/
∂
v.Without loss of generality, we consider onlyu-directed currents
(10)
J
S
u
(
u
,
v
)
=
1
J
S
(
u
,
v
)
∑
m
=
0
M
u
∑
n
=
0
N
v
a
m
n
u
C
~
m
P
~
m
(
u
)
C
n
P
n
(
v
)
,
where J
S
(
u
,
v
)
=
|
a
→
u
×
a
→
v
| is the surface Jacobian, a
m
n
u are unknown coefficients, M
u and N
v are the basis orders along the u-directed current flow direction and the transverse direction, respectively. P
n
(
v
) are Legendre polynomials, and P
~
m
(
u
) are the modified Legendre polynomial, which can be defined as
(11)
P
~
m
(
u
)
=
{
1
-
u
,
m
=
0
1
+
u
,
m
=
1
P
m
(
u
)
-
P
m
-
2
(
u
)
,
m
≥
2
C
~
m and C
n are the scaling factors and are defined as
(12)
C
~
m
=
{
3
4
,
m
=
0,1
1
2
(
2
m
-
3
)
(
2
m
+
1
)
2
m
-
1
,
m
≥
2
,
C
n
=
n
+
1
2
.Finally, applying Galerkin’s method to (8) in MoM, a matrix equation can be obtained as:
(13)
A
x
=
b
.
In (13), the element of the impedance matrix A is evaluated with the presented hierarchical basis functions. The matrix equation can be solved by the restart GMRES [38] iterative method using MLFMM to accelerate the matrix-vector multiply.


### 2.3. Hierarchical Two-Level Spectral Preconditioner

Though the use of high order basis functions reduces the number of unknowns, it still increases the condition number of the matrix system and decelerates the convergence of Krylov iterative methods. In order to speed up the convergence rate of Krylov methods, preconditioning techniques are employed to transform the EFIE matrix equations into an equivalent form [32]
(14)
M
h
A
h
x
=
M
h
b
,
where A
h is the EFIE impedance matrix associated with the higher order hierarchical Legendre basis functions, and M
h is a improved SAI preconditioner based on near-field elements of A
h in MLFMA [30].Although the SAI preconditioner can improve matrix conditions by clustering most of the large eigenvalues close to one but still leave a few close to the origin, which can potentially slow down the convergence of Krylov methods. In this paper, the hierarchical two-level spectral preconditioning method is used to improve the quality of a prescribed SAI preconditioner. It is based on the higher order hierarchical basis functions, which is used to damp the high frequencies of the error, while the low frequencies of the error is eliminated by a spectral preconditioner [36] in a two-level manner defined based on the lower order hierarchical basis functions.LetU
k be a set of eigenvectors of dimension n
l
×
k associated with the smallest eigenvalues of the preconditioned matrix M
h
A
l, where A
l denotes the EFIE impedance matrix associated with the lowerorder hierarchical basis functions. The second level spectral preconditioner can then be defined as
(15)
M
l
=
I
h
+
V
k
(
T
k
-
1
-
I
k
)
V
k
H
,
where T
k
=
V
k
(
M
h
A
l
)
(
V
k
)
H, V
k is dimension n
h
×
k generating from U
k by appending zeros and I
h and I
k are unit matrix of dimension n
h and k, respectively. The superscript H denotes the transpose and conjugate of a given complex matrix. Combining this second spectral preconditioner with the prescribed preconditoner in the two-level manner, a hierarchical two-level preconditioner is derived and the linear system to be solved can be transformed into
(16)
M
l
M
h
A
h
x
=
M
l
M
h
b
.
In order to evaluate approximations to smallest eigenvectors for constructing the second spectral preconditioner M
l, the SAI preconditioned GMRES-DR algorithm [39] is used to solve the coarse grid system based on the lower order hierarchical basis functions, which generates approximations to eigenvectors as a byproduct. The approximate eigenvectors in GMRES-DR span a small Krylov subspace and so are generated in a compact form
(17)
(
M
h
A
l
)
U
k
=
U
k
+
1
H
-
k
,
where U
k is a n
l
×
k matrix, whose columns span the subspace of approximate eigenvectors, U
k
+
1 is the same except an extra column and H
-
k is a full k
+
1 by k matrix. Note that (17) allows access to both the approximate eigenvectors and their products with SAI preconditioned matrix M
h
A
l while requiring storage of only k
+
1 vectors of length n
l. Therefore, in order to construct the spectral preconditioner in a two-level manner, one can simply replace V
k with U
k by appending zeros, T
k with H
k, where H
k is a full k by k matrix by discarding last row of H
-
k.Therefore, a hierarchical two-level spectral preconditioned GMRES algorithm is presented for solving systems of linear equations, as follows:(i)
Construct SAI preconditioning matrixM
h based on the higher order hierarchical basis functions.
(ii)
Solve the coarse grid system based on the lower order hierarchical basis functions with the SAI preconditioned GMRES-DR algorithm, and use generated eigenvector information to construct the spectral preconditioning matrixM
l.
(iii)
Construct the two-level spectral preconditioning matrixM
=
M
l
M
h, and use it for GMRES algorithm to solve linear systems.


## 2.1. Rough Surface Modeling and EFIE

As shown in Figure1, a perfectly electric conductor (PEC) cubic is located above a PEC rough surface. The rough surface is a Gaussian stationary stochastic process with a zero mean value, which can easily be generated by a spectral method. In order to eliminate the edge effects caused by truncation of the finite surface length, the tapered wave is usually employed [1]. A TE-polarized tapered wave can be expressed as
(1)
E
→
i
(
r
→
)
=
exp
⁡
[
-
i
k
(
z
cos
⁡
θ
i
+
x
sin
θ
i
cos
⁡
ϕ
i
+
y
sin
θ
i
sin
ϕ
i
)
h
h
h
h
h
h
×
(
1
+
w
)
(
z
cos
⁡
θ
i
+
x
sin
θ
i
cos
⁡
ϕ
i
+
y
sin
θ
i
sin
ϕ
i
)

]
×
exp
⁡
(
-
t
x
-
t
y
)
,
t
x
=
(
x
cos
⁡
θ
i
cos
⁡
ϕ
i
+
y
cos
⁡
θ
i
sin
ϕ
i
+
z
sin
θ
i
)
2
g
2
cos
⁡
θ
i
2
t
y
=
(
-
x
sin
ϕ
i
+
y
cos
⁡
ϕ
i
)
2
g
2
w
=
1
k
2
(
2
t
x
-
1
g
2
cos
⁡
2
θ
i
+
2
t
y
-
1
g
2
)
,
where g is the widith of the tapered wave, θ
i and ϕ
i are elevation angle and azimuth angle of the incident wave, respectively. L is truncated length of rough surface. The width of the tapered wave should be large enough to illuminate upon the surface [2, 5].Figure 1
Geometric model of EM scattering from the rough surface.When there is no object above the PEC rough surface, the induced currentJ
r
′
→
(
r
→
) on the rough surface is
(2)
J
r
′
→
(
r
→
)
=
2
n
^
×
H
→
i
(
r
→
)
,
where H
→
i
(
r
→
) denotes the incident magnetic field. When there is no object above the rough surface, the scattering field E
→
s
r
(
r
→
) above the rough surface can be written as
(3)
E
→
s
r
(
r
→
)
=
i
ω
μ
∫
S
2
G
→
→
0
(
r
→
,
r
→
′
)
·
J
r
′
→
(
r
→
)
d
S
′
,
where r
→ is the position point on the rough surface S
2 and r
→
′ is observation point. G
→
→
0
(
r
→
,
r
→
′
) is dyadic free space Green’s function
(4)
G
→
→
0
(
r
→
,
r
→
′
)
=
[
I
̿
-
1
k
2
∇
∇
′
]
e
i
k
|
r
→
-
r
→
′
|
|
r
→
-
r
→
′
|
.
When the object exists above the PEC rough surface, the scattering field E
→
s
o
(
r
→
) above the rough surface can be written as
(5)
E
→
s
o
(
r
→
)
=
∫
S
1
G
→
→
e
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
,
where J
→
o
(
r
→
) is the induced current on the surface S
1 of object, G
→
→
e
(
r
→
,
r
→
′
) denotes the dyadic Green’s function in rough surface [37] as the following:
(6)
G
→
→
e
(
r
→
,
r
→
′
)
=
i
ω
μ
{
∫
S
2
G
→
→
0
(
r
→
,
r
′′
→
)
·
{
2
n
^
×
[
∇
g
(
r
′′
→
,
r
′
→
)
×
I
-
-
]
}
d
s
′
′
G
→
→
0
(
r
→
,
r
→
′
)
h
h
h
h
h
h
h
h
h
+
∫
S
2
G
→
→
0
(
r
→
,
r
→
′′
)
·
{
2
n
^
×
[
∇
g
(
r
→
′′
,
r
→
′
)
×
I
-
-
]
}
d
s
′
′
}
.
Substituting G
→
→
e
(
r
→
,
r
→
′
) into (5) gives
(7)
E
→
s
o
(
r
→
)
=
∫
S
1
G
→
→
e
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
=
i
ω
μ
∫
S
1
G
→
→
0
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
+
i
ω
μ
∫
S
1
G
→
→
s
(
r
→
,
r
→
′
)
·
J
→
o
(
r
→
′
)
d
S
′
(8)
G
→
→
s
(
r
→
,
r
→
′
)
=
∫
S
2
G
→
→
0
(
r
→
,
r
→
′′
)
·
{
2
n
^
×
[
∇
g
(
r
→
′′
,
r
→
′
)
×
I
→
→
]
}
d
s
′′
.
The first term at the right side of (7) represents the scattering field without object above the rough surface, the second term represents the coupling interactions between the rough surface and the object.


## 2.2. Higher Order Hierarchical Legendre Basis Functions

Equations (7) can be solved by MoM. The factor that most limits the capability of the MoM is the number of unknowns. As was pointed out in the introduction, this limitation can be relaxed by using higher order basis functions. For a given accuracy, the use of higher order basis functions allows us to use larger triangular patches to discrete the objects. In this paper, higher order hierarchical Legendre basis Functions defined on curvilinear quadrilateral surface [24, 25] are chosen to represent the surface current J
→
o as
(9)
J
→
o
=
J
S
u
a
→
u
+
J
S
v
a
→
v
,
where a
→
u and a
→
v are the co-variant unitary vectors as a
→
u
=
∂
r
→
/
∂
u and a
→
v
=
∂
r
→
/
∂
v.Without loss of generality, we consider onlyu-directed currents
(10)
J
S
u
(
u
,
v
)
=
1
J
S
(
u
,
v
)
∑
m
=
0
M
u
∑
n
=
0
N
v
a
m
n
u
C
~
m
P
~
m
(
u
)
C
n
P
n
(
v
)
,
where J
S
(
u
,
v
)
=
|
a
→
u
×
a
→
v
| is the surface Jacobian, a
m
n
u are unknown coefficients, M
u and N
v are the basis orders along the u-directed current flow direction and the transverse direction, respectively. P
n
(
v
) are Legendre polynomials, and P
~
m
(
u
) are the modified Legendre polynomial, which can be defined as
(11)
P
~
m
(
u
)
=
{
1
-
u
,
m
=
0
1
+
u
,
m
=
1
P
m
(
u
)
-
P
m
-
2
(
u
)
,
m
≥
2
C
~
m and C
n are the scaling factors and are defined as
(12)
C
~
m
=
{
3
4
,
m
=
0,1
1
2
(
2
m
-
3
)
(
2
m
+
1
)
2
m
-
1
,
m
≥
2
,
C
n
=
n
+
1
2
.Finally, applying Galerkin’s method to (8) in MoM, a matrix equation can be obtained as:
(13)
A
x
=
b
.
In (13), the element of the impedance matrix A is evaluated with the presented hierarchical basis functions. The matrix equation can be solved by the restart GMRES [38] iterative method using MLFMM to accelerate the matrix-vector multiply.


## 2.3. Hierarchical Two-Level Spectral Preconditioner

Though the use of high order basis functions reduces the number of unknowns, it still increases the condition number of the matrix system and decelerates the convergence of Krylov iterative methods. In order to speed up the convergence rate of Krylov methods, preconditioning techniques are employed to transform the EFIE matrix equations into an equivalent form [32]
(14)
M
h
A
h
x
=
M
h
b
,
where A
h is the EFIE impedance matrix associated with the higher order hierarchical Legendre basis functions, and M
h is a improved SAI preconditioner based on near-field elements of A
h in MLFMA [30].Although the SAI preconditioner can improve matrix conditions by clustering most of the large eigenvalues close to one but still leave a few close to the origin, which can potentially slow down the convergence of Krylov methods. In this paper, the hierarchical two-level spectral preconditioning method is used to improve the quality of a prescribed SAI preconditioner. It is based on the higher order hierarchical basis functions, which is used to damp the high frequencies of the error, while the low frequencies of the error is eliminated by a spectral preconditioner [36] in a two-level manner defined based on the lower order hierarchical basis functions.LetU
k be a set of eigenvectors of dimension n
l
×
k associated with the smallest eigenvalues of the preconditioned matrix M
h
A
l, where A
l denotes the EFIE impedance matrix associated with the lowerorder hierarchical basis functions. The second level spectral preconditioner can then be defined as
(15)
M
l
=
I
h
+
V
k
(
T
k
-
1
-
I
k
)
V
k
H
,
where T
k
=
V
k
(
M
h
A
l
)
(
V
k
)
H, V
k is dimension n
h
×
k generating from U
k by appending zeros and I
h and I
k are unit matrix of dimension n
h and k, respectively. The superscript H denotes the transpose and conjugate of a given complex matrix. Combining this second spectral preconditioner with the prescribed preconditoner in the two-level manner, a hierarchical two-level preconditioner is derived and the linear system to be solved can be transformed into
(16)
M
l
M
h
A
h
x
=
M
l
M
h
b
.
In order to evaluate approximations to smallest eigenvectors for constructing the second spectral preconditioner M
l, the SAI preconditioned GMRES-DR algorithm [39] is used to solve the coarse grid system based on the lower order hierarchical basis functions, which generates approximations to eigenvectors as a byproduct. The approximate eigenvectors in GMRES-DR span a small Krylov subspace and so are generated in a compact form
(17)
(
M
h
A
l
)
U
k
=
U
k
+
1
H
-
k
,
where U
k is a n
l
×
k matrix, whose columns span the subspace of approximate eigenvectors, U
k
+
1 is the same except an extra column and H
-
k is a full k
+
1 by k matrix. Note that (17) allows access to both the approximate eigenvectors and their products with SAI preconditioned matrix M
h
A
l while requiring storage of only k
+
1 vectors of length n
l. Therefore, in order to construct the spectral preconditioner in a two-level manner, one can simply replace V
k with U
k by appending zeros, T
k with H
k, where H
k is a full k by k matrix by discarding last row of H
-
k.Therefore, a hierarchical two-level spectral preconditioned GMRES algorithm is presented for solving systems of linear equations, as follows:(i)
Construct SAI preconditioning matrixM
h based on the higher order hierarchical basis functions.
(ii)
Solve the coarse grid system based on the lower order hierarchical basis functions with the SAI preconditioned GMRES-DR algorithm, and use generated eigenvector information to construct the spectral preconditioning matrixM
l.
(iii)
Construct the two-level spectral preconditioning matrixM
=
M
l
M
h, and use it for GMRES algorithm to solve linear systems.


## 3. Numerical Experiments

In this section, the EFIE linear systems based on the presented hierarchical higher order Legendre basis functions are solved with MLFMM accelerated Krylov iterative methods. All numerical experiments are performed on a personal computer with Intel(R) Core(TM)2 Quad Q9500 2.99 GHz CPU and 4 GB RAM in single precision. The restarted version of GMRES (m) algorithm and the inner-outer Flexible GMRES algorithm (FGMRES) [40] are used as the iterative solvers. m is taken to be 30 in GMRES (m) algorithm. The inner and outer restart numbers of FGMRES are both 10. In the FGMRES algorithm, the required precision for the inner and outer iteration is 1.E-2, 1.E-3, respectively.Additional details and comments on the implementation are given below:(i)
zero vector is taken as initial approximate solution for all examples and all systems in each example
(ii)
the iteration process is terminated when the normalized backward error is reduced by 10−3 for all the examples.The first example is a PEC orthogonal plane scatterer consisting of each plane of size (8
λ
×
8
λ) as shown in Figure 2, where λ is the free-space wavelength. The scatterer is discretized with curvilinear quadrilateral patches for 2- and 3-order hierarchical Legendre basis functions with 11502 and 9072 unknowns, respectively. The average mesh sizes are chosen as 0.3λ for 2 order basis functions, and 0.5λ for 3-order basis functions. The incident angles of plane wave are ϕ
i
=
9
0
∘, θ
i
=
4
5
∘
. The bi-static RCS of the orthogonal plane scatterer with vertical polarization is given in Figure 1 for 2- and 3-order hierarchical Legendre basis functions. The results from FEKO software are also given in Figure 2 in order to verify the accuracy of the proposed the high order hierarchical Legendre basis functions. Good agreement is achieved between these two kinds of results. It can be seen that the use of the higher order hierarchical Legendre basis functions allows the number of unknowns to be reduced by a factor of 1.27.(a) Geometry of a PEC orthogonal plane scatterer, (b) The bistatic RCS with VV polarization for the orthogonal plane scatterer.
(a)
(b)In order to accelerate the convergence rate of GMRES algorithm for the EFIE system based on the hierarchical Legendre basis functions, the hierarchical two-level spectral preconditioning techniques are developed. Some numerical results are given to demonstrate the effectiveness of the hierarchical two-level spectral preconditioner for the solution of EFIE system. Figures3 and 4 show the convergence histories of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for the orthogonal plane scatterer in bistatic RCS computation. In the hierarchical two-level spectral preconditioned GMRES, k
=
20 approximate smallest eigenvectors, extracted by GMRES-DR algorithm during solving EFIE system, are employed to build the two-level spectral preconditioner M
l based on 1-order hierarchical Legendre basis functions for the first example. Table 1 further gives the construction time and solution time for different algorithms for orthogonal plane scatterer in bistatic RCS computation. In Table 1, “−” means that constructing time of the preconditioner is very few and to be ignored. Total time represents the sum of constructing time and solution time. It can be found from Figures 3-4 that the hierarchical two-level spectral preconditioned GMRES converges very fast than the FGMRES and GMRES. As shown in Table 1, though the additional construct time of the hierarchical two-level spectral preconditioner is needed, the hierarchical two-level spectral preconditioned GMRES decreases the solution time by a factor of 3.0 compared to FGMRES, a factor of 25 compared to GMRES for 2-order hierarchical Legendre basis functions. It is also found that the hierarchical two-level spectral preconditioned GMRES decreases the solution time by a factor of 4.0 compared to FGMRES, a factor of 53.0 compared to GMRES for 3-order ones. It can be concluded that the hierarchical two-level spectral preconditioning method improves the condition number of linear system based on high order hierarchical Legendre basis functions.Table 1
Construction time and solution time (in seconds) for the orthogonal plane scatterer.
Basis functions
Mesh sizes
Unknowns
Solution methods
Construction time
Iteration step
Solution time
Total time
2-order
0.3λ
11,502
GMRES
—
439
552
552
FGMRES
—
45
65
65
Two-level
69
17
22
91
3-order
0.5λ
9,072
GMRES
—
958
783
783
FGMRES
—
73
103
103
Two-level
32
18
15
47Figure 3
Convergence history of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for 2-order hierarchical Legendre basis functions for the orthogonal plane scatterer.Figure 4
Convergence history of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for 3-order hierarchical Legendre basis functions for the orthogonal plane scatterer.Next, a PEC paraboloid antenna is considered in Figure5. The size of aperture for the paraboloid antenna is 4.8λ and the focus is 4.813λ. The paraboloid antenna is discretized with curvilinear quadrilateral patches for 2- and 3-order hierarchical Legendre basis functions with 19992 and 17652 unknowns, respectively. The average mesh sizes are also chosen as 0.3λ for 2 order basis functions, and 0.5λ for 3-order basis functions. The incident angles of plane wave are ϕ
i
=
0
∘, θ
i
=
0
°. Figure 5 gives the bi-static RCS with vertical polarization for the paraboloid antenna. It is very clear that the results from 2- and 3-order hierarchical Legendre basis functions agree well with the results from FEKO. Figures 6 and 7 give the convergence histories of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for the paraboloid antenna in bistatic RCS computation. Table 2 further lists the construction time and solution time for different algorithms for the paraboloid antenna. In these computations, k
=
20 approximate smallest eigenvectors are employed to build the two-level spectral preconditioner M
l. It can be observed that the hierarchical two-level spectral preconditioning method can greatly improve the convergence. Compared to the GMRES, the hierarchical two-level spectral preconditioned GMRES decreases the total time by a factor of 7.5 for 2-order hierarchical Legendre basis functions, a factor of 14.0 for 3-order ones.Table 2
Construction time and solution time (in seconds) for the paraboloid antenna.
Basis functions
Mesh sizes
Unknowns
Solution method
Construction time
Iteration step
Solution time
Total time
2-order
0.3λ
19,992
GMRES
—
470
1,334
1334
FGMRES
—
52
179
179
Two-level
134
17
45
179
3-order
0.5λ
17,652
GMRES
—
1593
2,106
2106
FGMRES
—
111
355
355
Two-level
101
26
49
150(a) Geometry of a PEC paraboloid antenna. (b) The bistatic RCS with VV polarization for the paraboloid antenna.
(a)
(b)Figure 6
Convergence history of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for 3-order hierarchical Legendre basis functions for the paraboloid antenna.Figure 7
Convergence history of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for 3-order hierarchical Legendre basis functions for the paraboloid antenna.Finally, a PEC missile target above a rough surface in Figure8 is considered to further demonstrate the hierarchical two-level spectral preconditioning method, in which a Gaussian PEC rough surface with the following Gaussian spectrum [41]
(18)
W
(
k
x
,
k
y
)
=
h
2
l
x
l
y
4
π
exp
⁡
(
-
k
x
2
l
x
2
+
k
y
2
l
y
2
4
)
is used. Here, l
x and l
y are the correlation lengths in x-and y-directions, respectively, and h is the rms height of the rough surface. As shown in Figure 8, the dimensions of the rough surface are 16
λ
×
16
λ, with h
=
0.1
λ and l
x
=
l
y
=
1.5
λ. The tapered wave is incident at the elevation angle θ
i
=
3
0
0 and the azimuth angle ϕ
i
=
0
0. The width of the tapered wave is 4.0
λ. The dimension of the missile is 1.96
λ
×
10.5
λ
×
1.96
λ. The height of the missile is 10
λ above the rough surface. The PEC missile target and rough surface are both discretized with curvilinear quadrilateral patches for 2- and 3-order hierarchical Legendre basis functions with 55744 and 31836 unknowns, respectively. Figure 8 also gives the bistatic RCS for VV polarization of different methods, which shows a reasonably good agreement. Figures 9 and 10 give the convergence histories of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for the missile target above a rough surface. Table 3 further shows the construction time and solution time for different algorithms for missile target above a rough surface. In these computations, k
=
20 approximate smallest eigenvectors are also chosen to build the two-level spectral preconditioner M
l. It can be observed that the hierarchical two-level spectral preconditioned GMRES decreases the solution time by a factor of 6.6 compared to FGMRES, a factor of 19.4 compared to GMRES for 2-order hierarchical Legendre basis functions. It is also found that the hierarchical two-level spectral preconditioned GMRES decreases the solution time by a factor of 7.3 compared to FGMRES, a factor of 64.0 compared to GMRES for 3-order ones. It can be concluded that the hierarchical two-level spectral preconditioning method based on high order hierarchical Legendre basis functions is very efficient in analyzing electromagnetic scattering from rough surfaces. It can also be observed that the hierarchical two-level spectral preconditioning method based on 3-order hierarchical Legendre basis functions improves the condition number of linear system better than that based on 2-order ones.Table 3
Construction time and solution time (in seconds) for the missile target above a rough surface.
Basis functions
Mesh sizes
Unknowns
Solution method
Construction time
Iteration step
Solution time
Total time
2-order
0.3λ
55,744
GMRES
—
601
1938
1938
FGMRES
—
113
662
662
Two-level
618
31
100
718
3-order
0.5λ
31,836
GMRES
—
3441
10,685
10,685
FGMRES
—
191
1213
1213
Two-level
372
51
167
539(a) Geometric model of EM scattering from the rough surface (b) The bistatic RCS with VV polarization for the missile target above a rough surface.
(a)
(b)Figure 9
Convergence history of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for 2-order hierarchical Legendre basis functions for the missile target above a rough surface.Figure 10
Convergence history of the hierarchical two-level spectral preconditioned GMRES, FGMRES and GMRES algorithms for 3-order hierarchical Legendre basis functions for the missile target above a rough surface.


## 4. Conclusions

In this paper, the hierarchical two-level spectral preconditioning technique based on higher order hierarchical Legendre basis functions is presented for solving EFIE for scattering from conducting objects. The use of higher order basis functions leads to a reduction in the number of unknowns without compromising the accuracy of geometry modeling. Numerical experiments are performed and the comparison is made with the GMRES and FGMRES. It can be found that the proposed hierarchical two-level spectral preconditioning technique is more efficient and can significantly reduce the overall computational cost. It can be found that the hierarchical two-level spectral preconditioning technique is more efficient and can significantly reduce the overall computational cost.



---

*Source: 752418-2014-07-02.xml*