I. Introduction
In this paper, we introduce a fast method of moments (MoM) [1] solution for three-dimensional (3D) perfect electric conducting (PEC) scattering problems. The electric field integral equation (EFIE) has been a popular choice. The solution derived from the EFIE has higher accuracy compared to that of the magnetic field integral equation (MFIE). However, the impedance matrix of MFIE has a better convergence rate when solved with an iterative solver. The traditional MoM solutions from the EFIE or MFIE suffer from prohibitive O(N2) complexities of memory requirements and CPU time to assemble the impedance matrix and perform the matrix-vector multiplication with an iterative matrix solver. For complex structures, the convergence of the impedance matrix is a big issue. Many researchers are interested in the MFIE formulation having better accuracy [2, 3].
For electrically large problems, several fast algorithms have been developed to overcome these numerical complexities. Multilevel fast multipole method (MLFMM) [4] is the most powerful algorithm, which has O(N) and O(NlogN) complexities for memory and the matrix-vector multiplication time, respectively. However, it has a strong dependence on integral kernels. There are several algorithms that are less kernel-dependent. The algebraic methods, such as IE-QR [5] and adaptive cross approximation (ACA) [6], have been developed to compress merely the impedance matrix. From the physical point of view, there are equivalent source approximations and Green’s function approximations, which are both employed on a uniform Cartesian grid. Among the equivalent source approximation methods, the precorrected fast Fourier transform (p-FFT) [7] and the adaptive integral method (AIM) [8] are the most well-known algorithms.
This paper extends an IE-FFT algorithm [9] into the MFIE formulation for 3D PEC geometries with closed surfaces. The IE-FFT algorithm uses algebraically simple Lagrange polynomials for the free-space Green’s function on a Cartesian grid. Through separation variables, the gradient of the Green’s function consists of one coefficient matrix and two Π matrices; one is for the integrand of the product of the curl of the basis functions and Lagrange polynomials, and the other is for the integrand of the cross-product of the basis functions and the gradient of the Lagrange polynomials. This results in a non-symmetric MFIE formulation. The proposed algorithm leads to O(N1.5) complexity for the memory requirement and O(N1.5logN) complexity for the matrix-vector multiplication. Even though the MFIE has an accuracy problem, it can yield reliable solutions with careful treatment.
This paper is organized as follows. Section II provides a description of the MFIE formulation. The detailed implementation of the IE-FFT algorithm is described in Section III. Through numerical examples, Section IV demonstrates the accuracy and performance of the proposed method. Finally, the paper is concluded in Section V.
II. MFIE Formulation
The MFIE formulation is briefly shown for an arbitrarily shaped 3D PEC object. The formulation is directly used in the computation of the near-field correction for the IE-FFT algorithm to ensure its accuracy. The MFIE formulation can be written from the boundary condition for the tangential magnetic field on closed surfaces as
To begin with, the discrete Galerkin statement for MFIE is shown below:
(2)
where Γh denotes the faceted surface of the PEC object, Xh is the finite dimensional trial and testing space, and λ⃗ (⇉) is the discrete Galerkin testing function.
(3)
The unknown current density induced on the surface is
where α⃗i(⇉) represents surface div-conforming Rao-Wilton-Glisson (RWG) vector basis functions [10]. The entries of the impedance matrix, Z, are given by
where
(6)
and
where N is the number of unknowns; note that supp() indicates the finite support of every non-boundary, edge-related basis function. Here, Dij and Pij are singular and coupling entries of the impedance matrix from the discrete Galerkin statement.
III. IE-FFT Algorithm
The IE-FFT algorithm makes a hexahedron bounding box that encloses the entire geometry in Fig. 1. A non-uniform triangular mesh for the RWG basis functions and a uniform Cartesian grid for the free-space Green’s functions are shown in two discretizations. Note that α is a constant used to define the near-field correction region, and λ is the wavelength. d is the sampling resolution. Here, L is the size of the second order Cartesian element.
The details of the IE-FFT algorithm are shown below.
1. A Uniform Cartesian Representation of Free-Space Green’s Function using Lagrange Polynomials
The free-space Green’s function is written in the matrix form:
where
(9)
and where the number of grid points is Ng =Nx × Ny ×Nz. Also, the dimensional indices could be expressed as n = (i, j,k) and n′=(i′,j′,k′) , where 0 ≤ i,i′< Nx , 0≤ j, j′ < Ny , and 0 ≤k k′, <Ny . The pth order interpolation basis functions,
β n p , are the 3D tensor products form of the one-dimensional piecewise Lagrange polynomials on a Cartesian grid:
(12)
where gn,n ′ is the Lagrange coefficients of the free-space Green’s function. Interchanging summation and integration orders leads to
2. Representation of the Π Matrices
There are two projection matrices needed in the IE-FFT. They are:
and
respectively. In contrast to Eq. (3), ∇′g(⇉;⇉′) only depends on the Lagrange polynomials, i.e.,
∇ ′ β n p ( r → ′ ) . The gradient of the 3D tensor product,
∇ β n p ( r → ) , is expressed in
where
(17)
The entries of Π⃗P are
(18)
where α⃗i,x (⇉), αi,y(⇉), and α⃗i,z(r⃗) are the vectors of the RWG basis function at the x-, y-, z-directions, respectively. Note that Π⃗p is a vector-valued and sparse matrix.
3. Near-Field Correction
In Fig. 1, the near-field interaction terms within αλ should be appropriately corrected to guarantee the accuracy. The correction entries are given as:
where 0 ≤i<N, j ∈ Lneig , and Lneig comprise the set of the near-field interaction elements.
4. Fast Matrix Vector Multiplication
The complexities of the Zcorr and Π matrices concerning the memory requirements and the matrix fill-in time are O(N). With the help of the FFT, the complexity of the matrix-vector multiplication of the G matrix leads to O(N1.5logN). The memory requirement of the G matrix is O(N1.5).
IV. Numerical Results
To demonstrate the efficiency of the proposed algorithm, a PEC sphere with a radius of 1.0 m is considered. The geometry of the PEC sphere is shown in Fig. 2. The triangular meshes are built so that there are at least λ/7. All numerical experiments are carried out on a 2 GB RAM Intel Pentium M processor 1.60 GHz. All computations have been performed in single precision arithmetic. Third-order Lagrange polynomials are used to interpolate the free-space Green’s function.
The results of the IE-FFT algorithm with the MFIE formulation are compared to those of the Mie series. Fig. 3 shows the results of the bistatic RCS at a frequency of 300 MHz. Three results of the Mie series, the conventional MoM, and the proposed approach are compared. In Fig. 3(a), the results between the Mie series and the MoM approaches are seen to be slightly different around 180°. However, the results between the traditional MoM and the IE-FFT algorithm have very good agreements on both the E-plane and the H-plane. Inaccuracy comes from the numerical integration in the hyper-singular part. The IE-FFT algorithm does not deteriorate the accuracy. The results of the bistatic RCS at a frequency of 600 MHz are shown in Fig. 4. The results from the Mie series and the IE-FFT algorithm also have reasonable agreements on both the E-plane and the H-plane. The largest difference between the two results is obtained around 160°–180° from the effects of the numerical integration. Fig. 5 shows the results of bistatic RCS at a frequency of 1,200 MHz. Both results are reasonable agreements.
Table 1 summarizes the memory requirements of the IE-FFT algorithm for third-order Lagrange polynomials. All units are Megabytes. The memory of the correction matrix, Zcorr , and the Π matrices shows O(N) complexity. However, the coefficient of the free-space Green’s function is O(N1.5) complexity.
Table 2 summarizes the CPU time and the number of iterations of the IE-FFT algorithm with third-order Lagrange polynomials. The CPU time for the matrices fill-in has O(N) complexity. The CPU time for the matrix vector multiplication (MXV) is O(N1.5logN) complexity.
The memory requirement versus the number of unknowns is given in Fig. 6(a) for third-order Lagrange polynomials. The memory requirements of the correction, Π matrices, and the coefficients of the free-space Green’s function are plotted with circles, squares, and diamonds, respectively. The O(N) and O(N1.5) complexities are plotted as dashed and dotted lines for references, respectively. The CPU time for the matrix-fill-in and the matrix vector multiplication per iteration versus the number of unknowns are plotted in Fig. 6(b). As an iterative solver, a generalized minimal residual method (GMRES) [11] is used when the matrix vector products are performed. There is no preconditioner. The tolerance of GMRES is 10−3. The dashed and dotted lines of the O(N) and O(N1.5logN) complexities are plotted as references, respectively. The CPU time for assembling the correction Π matrices is O(N)complexity. The CPU time of MXV is approximately O(N1.5logN).
The accuracy of the IE-FFT algorithm for the MFIE formulation is addressed. The root mean square (RMS) error of the bistatic RCS is defined as
where θ and φ are the azimuth and elevation angles, RCSA (θ,φ) is the RCS value of the conventional MoM, the IE-FFT algorithm [9], and other numerical methods. First, we calculate the RMS error of the conventional MoM, relative to the Mie series solution versus the sampling segments per wavelength. The value of the error is the maximum error bound of the IE-FFT. For example, the RMS error of the bistatic RCS for a one-meter PEC sphere at a frequency of 600 MHz is 0.0108. Due to the hyper-singular integral of the MFIE formulation, the RMS error is much larger than that of the EFIE. The RMS errors of the IE-FFT, relative to the Mie series sampling segments per wavelength, are plotted in Fig. 7. The dashed line is the RMS error of the conventional MoM as a reference. The dash-dotted line with square markers and the solid line with circular markers represent the RMS error of the IE-FFT for the second- and third-order Lagrange polynomials, respectively. The RMS error of the second-order polynomials is converged with that of the conventional MoM with approximately 28 sampling segments. However, the RMS error of the third-order polynomials is converged with 19 elements. In this case, the RMS error for the MFIE is approximately 0.01. Some discrepancies are not the problem of the IE-FFT but that of the conventional MoM. The accuracy of the IE-FFT algorithm can be compared to that of the conventional MoM.
V. Conclusion
The IE-FFT algorithm with MFIE formulation achieves O(N1.5) and O(N1.5logN) complexities for required memory and CPU time, respectively. Also, it is shown that the proposed algorithm is highly efficient without the help of a preconditioner. The IE-FFT algorithm with MFIE formulation provides a high convergence rate as well. For better accuracy, a new scheme of hyper-singular integration should be further considered.