J. Electromagn. Eng. Sci Search


J. Electromagn. Eng. Sci > Volume 19(1); 2019 > Article
Seo: An IE-FFT Algorithm to Analyze PEC Objects for MFIE Formulation


An IE-FFT algorithm is implemented and applied to the electromagnetic (EM) solution of perfect electric conducting (PEC) scattering problems. The solution of the method of moments (MoM), based on the magnetic field integral equation (MFIE), is obtained for PEC objects with closed surfaces. The IE-FFT algorithm uses a uniform Cartesian grid to apply a global fast Fourier transform (FFT), which leads to significantly reduce memory requirement and speed up CPU with an iterative solver. The IE-FFT algorithm utilizes two discretizations, one for the unknown induced surface current on the planar triangular patches of 3D arbitrary geometries and the other on a uniform Cartesian grid for interpolating the free-space Green’s function. The uniform interpolation of the Green’s functions allows for a global FFT for far-field interaction terms, and the near-field interaction terms should be adequately corrected. A 3D block-Toeplitz structure for the Lagrangian interpolation of the Green’s function is proposed. The MFIE formulation with the IE-FFT algorithm, without the help of a preconditioner, is converged in certain iterations with a generalized minimal residual (GMRES) method. The complexity of the IE-FFT is found to be approximately O(N1.5) and O(N1.5logN) for memory requirements and CPU time, respectively.

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:
FindJh(r)XhH-1/2(divΓ;Γ)suchthat12Γhλh(r)·Jh(r)dΓ-Γh(λh(r)×n^)·ΓhJh(r)×g(r;r)dΓdΓ=Γhλh(r)·[n^×Hinc(r)]dΓ         λhXh,
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.
H-1/2(divΓ;Γ)={v|v(L2(Γ))2,divΓvL2(Γ)} is the correct spaces where an unknown current resides. and ′ are observation and source points, respectively, and &Hrarr;inc (⇉) represents the incident magnetic field. In the present application, the free-space Green’s function, g(r;r)=e-jk0|r-r|4π|r-r|, is considered. For the traditional MoM, Eq. (2) could be expressed as
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
Zij=12Dij-Pij,         0i,jN-1
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:
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, βnp, are the 3D tensor products form of the one-dimensional piecewise Lagrange polynomials on a Cartesian grid:
The entries of G are the 3D block-Toeplitz matrix. Combined with Eqs. (6) and (8),
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:
respectively. In contrast to Eq. (3), ∇′g(;′) only depends on the Lagrange polynomials, i.e., βnp(r). The gradient of the 3D tensor product, βnp(r), is expressed in
The entries of Π⃗P are
where α⃗i,x (&rrarr;), αi,y(&rrarr;), 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, jLneig , 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
η(A)=02π0π|RCSA(θ,φ)-RCSMie(θ,φ)|2sin θdθdφ02π0π|RCSMie(θ,φ)|2sin θdθdφ.
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.

Fig. 1
Two discretizations for unknown current density and the free-space Green’s function.
Fig. 2
The geometry of a PEC sphere.
Fig. 3
The bistatic RCS for a 1-m PEC sphere at a frequency of 300 MHz. (a) E-plane and (b) H-plane.
Fig. 4
The bistatic RCS for a one-meter PEC sphere at a frequency of 600 MHz. (a) E-plane and (b) H-plane.
Fig. 5
The bistatic RCS for a one-meter PEC sphere at a frequency of 1,200 MHz. (a) E-plane and (b) H-plane.
Fig. 6
The numerical complexities versus the number of unknowns (p = 3) (a) Memory requirements. (b) The CPU time for the matrix-fill-in and matrix-vector products per iteration.
Fig. 7
The RMS errors of the bistatic RCS calculations versus the sampling segments per wavelength (p = 2, 3).
Table 1
Memory requirement of the IE-FFT algorithm for scattering from a PEC sphere with a radius of 1 m
Freq. (MHz) N Zcorr Π⃗A + Π⃗P G
300 3,072 22 11 0.26
600 12,288 90 42 2.10
1,200 49,152 365 169 16.78
Table 2
The CPU time and the number of iterations of the IE-FFT algorithm for scattering from a PEC sphere with a radius of 1 m
Freq. (MHz) N Zcorr Π⃗A + Π⃗P MXV/iteration No. of iteration
300 3,072 130 4 0.26 19
600 12,288 540 17 2.10 79
1,200 49,152 2,105 19 16.78 96


1. RF Harrington, Field Computation by Moment Methods. New York, NY: The Macmillan Company, 1968.

2. RE Hodges and Y Rahmat-Samii, "The evaluation of MFIE integrals with the use of vector triangle basis functions," Microwave and Optical Technology Letters, vol. 14, no. 1, pp. 9–14, 1997.
3. O Ergul and L Gurel, "Improved testing of the magnetic-field integral equation," IEEE Microwave and Wireless Components Letters, vol. 15, no. 10, pp. 615–617, 2005.
4. JM Song and WC Chew, "Multilevel fast-multipole algorithm for solving combined field integral equations of electromagnetic scattering," Microwave and Optical Technology Letters, vol. 10, no. 1, pp. 14–19, 1995.
5. SM Seo and JF Lee, "A single-level low rank IE-QR algorithm for PEC scattering problems using EFIE formulation," IEEE Transactions on Antennas and Propagation, vol. 52, no. 8, pp. 2141–2146, 2004.
6. K Zhao, MN Vouvakis, and JF Lee, "Application of the multilevel adaptive cross-approximation on ground plane designs," In: Proceedings of 2004 International Symposium on Electromagnetic Compatibility (EMC); Silicon Valley, CA. 2004;pp 124–127.
7. JR Phillips and JK White, "A precorrected-FFT method for electrostatic analysis of complicated 3-D structures," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 10, pp. 1059–1072, 1997.
8. E Bleszynski, M Bleszynski, and T Jaroszewicz, "AIM: adaptive integral method for solving large-scale electromagnetic scattering and radiation problems," Radio Science, vol. 31, no. 5, pp. 1225–1251, 1996.
crossref pdf
9. SM Seo, C Wang, and JF Lee, "Analyzing PEC scattering structure using an IE-FFT algorithm," ACES Journal (The Applied Computational Electromagnetic Society Journal), vol. 24, no. 2, pp. 116–128, 2009.

10. S Rao, D Wilton, and A Glisson, "Electromagnetic scattering by surfaces of arbitrary shape," IEEE Transactions on Antennas and Propagation, vol. 30, no. 3, pp. 409–418, 1982.
11. GH Golub and CF Van Loan, Matrix Computations. Baltimore, MD: The Johns Hopkins University Press, 1996.


Seung Mo Seo received the B.S. degree from Hongik University in 1998 and the M.S. and Ph.D. degrees from the Ohio State University in 2001 and 2006, respectively, all in electrical engineering. From 1999 to 2006, he was a Graduate Research Associate with the ElectroScience Laboratory (ESL) in the Department of Electrical and Computer Engineering, the Ohio State University, Columbus, where he focused on the development of fast integral equation methods. From 2007 to 2010, he was Senior Engineer at the Digital Media and Communication (DMC) R&D Center of Samsung Electronics, where he developed RF circuit and antenna designs and simulations. From 2011 to the present, he has worked as a Senior Researcher at the Agency for Defense Development. His current research interest is computational electromagnetics.
Share :
Facebook Twitter Linked In Google+
METRICS Graph View
  • 5 Crossref
  • 3 Scopus
  • 4,956 View
  • 98 Download
Related articles in JEES


Browse all articles >

Editorial Office
#706 Totoo Valley, 217 Saechang-ro, Yongsan-gu, Seoul 04376, Korea
Tel: +82-2-337-9666    Fax: +82-2-6390-7550    E-mail: admin-jees@kiees.or.kr                

Copyright © 2024 by The Korean Institute of Electromagnetic Engineering and Science.

Developed in M2PI

Close layer
prev next