A Novel Scheme with FG-FFT for Analysis of Electromagnetic Scattering from Large Objects.
Method of Moments (MoM)  is a popular tool for the analysis of electromagnetic scattering and radiation by an object. However, the scope of its application is limited due to the high complexity. A number of methods, usually called fast algorithms, are proposed to reduce the computation complexity of the MoM. The traditional fast algorithms of MoM include three categories: methods based on the addition theorem [2-4], methods based on Fast Fourier Transformation (the FFT-based methods) [5-7], and the methods based on matrix-compression algorithm [8-10]. Due to its high universality, the FFT-based methods are widely used and studied in depth [11, 12].
Because FG-FFT is more concise and accurate in the FFT-based methods, this method is further studied and developed in recently years [13-15]. The memory requirement and computational complexity of the FFT-based methods are O([N.sup.1.5]) and 0([N.sup.1.5] log N) for surface integral equation, respectively. It is well known that the FFT-based methods still have some problems for electrically large targets: the fine grid spacing can reduce the number of the near correction matrix elements but increase the burden of FFT. Instead, the coarse grid spacing can significantly reduce the burden of FFT but dramatically increase the number of the near correction matrix elements. In order to alleviate this contradiction, in this paper, the numerical calculation method of near element is intensively researched.
The vast experimental data is obtained to find out a phenomenon: in near field, when the singularity of fitting Green's function is replaced with different replacement values, the accuracy of the fitting results shows significant difference. An optimal replacement value can reduce the fitting errors of the near elements. The near element refers to the intersecting element of the expansion box of both the basis function and the testing function under the uniform Cartesian grid.
As is shown in this paper, when the optimal replacement scheme is used in the FG-FFT, the near elements can keep a relatively high fitting accuracy within a certain range. Within this range the near element need not be corrected by MoM and these near elements belong to far matrix, which means that the novel scheme can dramatically reduce the number of the near correction matrix elements. The memory requirement and the filling time of the near matrix as well as the time of iterative computation are also reduced.
2.1. FFT-Based Methods. Considering an arbitrarily shaped 3D perfect electrical conductor (PEC) object illuminated by an incident plane wave [E.sup.i], the electric field integral equation (EFIE) on the surface [partial derivative][OMEGA] of the object can be given as follows:
[E.sup.i][|.sub.t] = [j[k.sub.0][[eta].sub.0] [[integral].sub.[partial derivative][OMEGA]] (J (r') + 1/[k.sup.2.sub.0] [nabla][nabla]' x J (r')) x G (r, r') ds'][|.sub.t], (1)
where J (rr) is the equivalent surface electric current, [[eta].sub.0] and [k.sub.0] are the wave impedance and the wave number in the free space, respectively, and G(r, r') denotes Green's function in the free space, which can be written as
[mathematical expression not reproducible]. (2)
After the application of the MoM, the EFIE can be converted into a matrix equation
ZI = V, (3)
where Z, I, and V represent the MoM-Matrix, the current coefficients vector, and the excitation vector, respectively.
In the FFT-based methods, Z can be split into two parts
Z [approximately equal to] ([Z.sup.near.sub.MoM] - [Z.sup.near.sub.FFT]) + [Z.sub.FFT] [??] [Z.sup.near] + [Z.sup.far], (4)
where [Z.sup.far] is the far matrix and can be rewritten as
[Z.sup.far] - j[k.sub.0][[eta].sub.0] [PI] x G x [[PI].sup.T] - j [[eta].sub.0]/[k.sub.0] [[PI].sub.d] x G x [[PI].sup.T.sub.d], (5)
where [PI] and [[PI].sub.d] are the coefficient transformation matrices; G is a triple Toeplitz matrix related to Green's function. The matrix-vector product of [Z.sup.far] can be sped up by FFT in the FFT-based methods. It should be noted that [Z.sup.far] includes not only the far field elements, but also the near field elements. [Z.sup.far] is called the far matrix because of the approximation for the far field elements and the inaccurate for the near field elements. In order to ensure the accuracy of near field elements, there must be corrections. Hence, [Z.sup.near] [+ or -] ZJMOM - ZnFT is the near correction sparse matrix. The every element of the [Z.sup.near] must be directly calculated and stored, due to which the majority of memory requirement and computational time are consumed for [Z.sup.near].
2.2. FG-FFT. In order to obtain the projection coefficients, the following overdetermined equation (6) is solved in FG-FFT 
[mathematical expression not reproducible], (6)
where [C.sub.n] is the expansion box of r' and p are a group of sample points. v is the grid nodes of [C.sub.n]. The projection coefficients [mathematical expression not reproducible] are to be determined (see Figure 1).
3. Replacement Scheme for the Fitting Singularity
In the FFT-based methods, the far elements as shown in Figure 2(a) with the separated expansion boxes between the basis function and the testing function can be approximated by (5). However, if the near elements as shown in Figure 2(b) with the intersection expansion boxes between the basis function and the testing function also were calculated by (5), the singularity of fitting Green's function would emerge at coincident points. In order to implement the numerical calculation, the traditional method uses a constant at random to replace the singular value at coincident points and then uses MoM to correct these elements. Therefore, in the traditional method, the near elements must belong to the near field correction matrix. In this section, through the analysis of experiment data, the effect of different replacement values on the fitting accuracy of the near elements is studied.
(i) The Experiment for Different Replacement Values. The 14 intervals [h/2 + (h/4) xi, h/2 + (h/4) x (i+1)], i = 0 ... 13, are chosen and 1000 points in each interval are randomly chosen as the distances between field points r and source points r' which are denoted by d. Meanwhile, field point r and source point r' are generated randomly for each d. The grid spacings for expansion boxes of field point r and source point r' are both h, and the orders are both M = 2. Starting point of the expansion box [C.sub.m] of field point r is set as ([r/h] - (1,1,1)) x h while that of the expansion box [C.sub.n] of source point r' is set as ([r'/h] - (1,1,1)) x h. Here [x] represents the rounding down operation. Fitting Green's function between r and r' is expressed as
[mathematical expression not reproducible], (7)
where coefficients ([mathematical expression not reproducible]) are both calculated with the FG-FFT . v is the Cartesian grid nodes within [C.sub.n], whereas u is the Cartesian grid nodes within [C.sub.m]. When r and r are very close, their corresponding expansion boxes [C.sub.m] and [C.sub.n] intersect each other. That is, [there exists]u [member of] [C.sub.m] and [there exists]v [member of] [C.sub.n] s.t. R = [parallel]u - v[parallel] = 0. Singularity will appear in the right side of (7). To avoid this, traditional FFT-based fast algorithms often consider that a smaller distance R' should be selected instead of R = 0 in the calculation of Green's function. However, there is no research about the effect of different replacement values R' on the fitting accuracy of the near elements in other papers. To better distinguish the influences of different replacement values, R' = 0.002[lambda], R' = 0.2[lambda], and R' = h/4 are chosen, respectively. Here, [lambda] denotes the wavelength of the free space. On these 14000 random distances, fitting Green's functions are calculated, as well as corresponding accurate Green's function point set as shown in Figure 3. The root mean square errors (RMSEs) of the real parts of fitting Green's functions in partial intervals are recorded in Table 1. RMSE is defined as
RMSE = [square root of (1/K [K.summation over (m=1)] [absolute value of RE ([G.sup.F] ([r.sub.m], [r'.sub.m]) - G ([r.sub.m], [r'.sub.m]))].sup.2])], (8)
where K is the number of points in every interval. Hence K = 1000 in this example.
The following conclusions can be drawn from Figure 3 and Table 1:
(1) Whether R' is 0.002[lambda], 0.2[lambda], or h/4, completely coincident points between the imaginary parts of fitting values and the imaginary parts of accurate values suggest very high fitting accuracy of the imaginary parts, so the fitting error is mainly from real parts.
(2) Replacement value should not be too large or too small. Due to the space limitations, we cannot present more influences of the different replacement values on fitting errors. Nevertheless, through a large number of experimental data, we can demonstrate that R' = h/4 is the optimal replacement value for fitting Green's function in the statistical sense. During numerical calculation, we replace R = 0 with R' = h/4, which brings minimization of fitting errors.
(3) From Table 1, we find that the error level is lower than [10.sup.-3] when d > 1.75h and R' = h/4. So presumably fitting Green's function within this range is approximately equal to accurate Green's function value and thus does not need correction. Therefore, when the optimal replacement value R' = h/4 is applied to the FG-FFT, the element is regarded as the far matrix element if the nearest distance between testing function [[psi].sub.m] and basis function [[psi].sub.n] is greater than 1.75h. Otherwise the element is regarded as the near correction matrix element. In this paper 1.75h is called the threshold between near field and far field. This allows a large number of near elements to be fitted directly without correction. In other words, part of near elements no longer belong to the near correction matrix. Hence, the optimal replacement scheme greatly decreases the memory requirements of near correction matrix, thereby reducing the filling time and per iteration time.
In order to apply the optimal replacement value to the FG-FFT algorithm, we first define the optimal replacement of Green's function:
[mathematical expression not reproducible] (9)
where R = [parallel]u - v[parallel], R' = h/4. And (5) needs to be rewritten as
[Z.sup.far] = j[k.sub.0][[eta].sub.0][PI] x G' x [[PI].sup.T] - j[[eta].sub.0]/[k.sub.0] [[PI].sub.d] x G' x [[PI].sup.T.sub.d] (10)
The optimal replacement scheme refers to the FG-FFT with (10), and at the same time the 1.75h is regarded as threshold between near field and far field.
4. Numerical Results
In this section, several numerical examples are introduced to demonstrate the efficiency and accuracy of the new scheme. The grid spacing is h. The expansion order is M = 2. If [[psi].sub.m]([[psi].sub.n]) is testing (basis) function, then [C.sub.m] ([C.sub.n]) denotes the expansion box enclosing it. In traditional FFT-based methods, an element is a near element if and only if [C.sub.m] intersects with [C.sub.n]. EFIE is adopted by the following examples. Besides, the 8 CPU parallel computing is used and the FFT codes are from the FFTW . For simplicity, [T] and [O] denote the implements of the FG-FFT with the traditional replacement scheme and the optimal replacement scheme, respectively.
Example A (a PEC sphere). In terms of the comparison of the traditional FG-FFT , the scattering from a PEC sphere of radius is 5[lambda] calculated. Discretized with about 10 elements per wavelength, the sphere can produce 113421 RWG functions. The bistatic RCS curves obtained by the Mie series, the FG-FFT[T], and the FG-FFT[O] are all shown in Figure 4.
It is seen form Figure 4 that these RCS curves coincide with h = 0.1[lambda] and h = 0.2[lambda], thus demonstrating the correctness of the proposed scheme. Some related data are recorded in Table 2, where the root mean square error (RMSE) is defined as
RMSE = [absolute value of 1/K [K.summation over (m=1)] [RCS.sup.Calcuated.sub.m] - [RCS.sup.*.sub.m]].sup.2] (11)
where K is the number of the azimuth angle samples. In this example [RCS.sup.*.sub.m] is the Mie series solution.
Example B (a PEC aircraft-like model). In order to verify the effectiveness of the new scheme for general objects with h = 0.2[lambda], the scattering from a PEC aircraft-like model is calculated. The aircraft-like model is shown in Figure 5. Moreover, discretized with about 10 elements per wavelength, it can produce 188865 RWG functions. The bistatic RCS curves obtained by the P-FFT (h = 0.1[lambda]), the FG-FFT[T] (h = 0.2[lambda]), and the FG-FFT[O] (h = 0.2[lambda]) with the optimal replacement scheme are all shown in Figure 5. In this example the bistatic RCS curves obtained by the P-FFT (h = 0.1[lambda]) is used as a reference curve. It is seen form Figure 5 that the three RCS curves coincide, thereby demonstrating the correctness of the proposed scheme for general objects. Some related data are recorded in Table 2, where RMSE is defined as (11) and in this example [RCS.sup.*.sub.m] is the solution of P-FFT (h = 0.1[lambda]).
From Figures 4 and 5 and Table 2, we can reach the following conclusions:
(1) From the data of Ex A in Table 2, in the optimal replacement scheme, the total memory requirement and CPU time decrease with the increase of the grid spacing. Therefore, the coarse grid (h = 0.2A) is a good choice for electrically large targets.
(2) From the data of Table 2, in the case of the optimal replacement scheme with h = 0.2[lambda], the memory requirement of the near field correction matrix is reduced by about 55%~ 60%, and the total memory requirement is reduced by about 35%, compared with traditional replacement scheme. At the same time, the filling time of the correction matrix is reduced by 55%~60%, and the per iteration time and the total time are also reduced. The computational efficiency of FG-FFT is greatly improved.
This paper first uses vast experimental data to show the effect of different replacement values on the fitting accuracy of Green's function of near element and then finds out the optimal replacement value R' = h/4. Experimental results show that the optimal replacement scheme with h = 0.2[lambda] can reduce the total memory requirement by about 35%, and at the same time the memory requirement and the filling time of the near field correction matrix are reduced by about 55%~60%, compared with traditional replacement scheme. The research in this paper breaks away from the traditional view that the near elements must need correction, and the computational efficiency of the FFT-based method can be significantly improved. The optimal replacement scheme in this paper can relieve the large memory requirement with the coarse grid in FG-FFT for electrically large targets. So it has a good prospect of application.
Conflicts of Interest
The authors declare that there are no conflicts of interest regarding the publication of this paper.
This work was supported by the Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (no. 15KJB510014), National Science Foundation for Outstanding Young Scholar of China (no. 61722101), Ph.D. Research Startup Foundation of Nanjing Institute of Technology (no. YKJ201443 and no. YKJ201444), and Open Research Program of State Key Laboratory of Millimeter Waves in Southeast University (no. K201718 and no. K201731).
 R. F. Harrington, Field Computation by Moment Methods, Macmillan, New York, NY, USA, 1968.
 C. C. Weng, T. J. Cui, and J. M. Song, "A FAFFA-MLFMA algorithm for electromagnetic scattering, Antennas Propagat. Mag," IEEE, vol. 50, no. 11, pp. 1641-1649, 2002.
 J. Aronsson and V. Okhmatovski, "Vectorial low-frequency MLFMA for the combined field integral equation," IEEE Antennas and Wireless Propagation Letters, vol. 10, pp. 532-535, 2011.
 H.-L. Sun, C.-M. Tong, and P. Peng, "Analysis of scattering from composite conductor and dielectric objects using single integral equation method and MLFMA based on JMCFIE," Progress In Electromagnetics Research M, vol. 52, pp. 141-152, 2016.
 S. Peng and C.-F. Wang, "Precorrected-FFT method on graphics processing units," Institute of Electrical and Electronics Engineers. Transactions on Antennas and Propagation, vol. 61, no. 4, part 2, pp. 2099-2107, 2013.
 S. Seung Mo and J. F. Lee, "A fast IE-FFT algorithm for solving PEC scattering problems, Trans. Magn," IEEE, vol. 41, no. 5, pp. 1476-1479, 2005.
 J.-Y. Xie, H.-X. Zhou, W. Hong, W.-D. Li, and G. Hua, "A novel FG-FFT method for the EFIE," in Proceedings of the International Conference on Computational Problem-Solving (ICCP '12), pp. 111-115, October 2012.
 L. Ma, Z. Nie, J. Hu, and S. He, "Combined MLFMA--ACA algorithm application to scattering problems with complex and fine structure," in Proceedings of the Asia Pacific Microwave Conference 2009, APMC 2009, pp. 802-805, December 2009.
 X.-M. Pan, J.-G. Wei, Z. Peng, and X.-Q. Sheng, "A fast algorithm for multiscale electromagnetic problems using interpolative decomposition and multilevel fast multipole algorithm," Radio Science, vol. 47, no. 1, Article ID RS1011, 2012.
 M. Li, M. A. Francavilla, F. Vipiana, G. Vecchi, Z. Fan, and R. Chen, "A doubly hierarchical mom for high-fidelity modeling of multiscale structures," IEEE Transactions on Electromagnetic Compatibility, vol. 56, no. 5, pp. 1103-1111, 2014.
 W.-B. Kong, H.-X. Zhou, K.-L. Zheng, and W. Hong, "Analysis of Multiscale Problems Using the MLFMA with the Assistance of the FFT-Based Method," IEEE Transactions on Antennas and Propagation, vol. 63, no. 9, pp. 4184-4188, 2015.
 J. Yin, J. Hu, Z. Nie, X. Feng, and S. He, "Floating interpolation stencil topology-based IE-FFT algorithm," Progress In Electromagnetics Research M, vol. 16, pp. 245-259, 2011.
 J.-Y. Xie, H.-X. Zhou, W. Hong, W.-D. Li, and G. Hua, "A highly accurate FGG-FG-FFT for the combined field integral equation," Institute of Electrical and Electronics Engineers. Transactions on Antennas and Propagation, vol. 61, no. 9, pp. 4641-4652, 2013.
 J. Xie, H. Zhou, X. Mu, G. Hua, W. Li, and W. Hong, "P-FFT and FG-FFT with real coefficients algorithm for the EFIE," Journal of Southeast University (English Edition), vol. 40, no. 3, pp. 267-270, 2014.
 H.-L. Sun, C. M. Tong, P. Peng, G. X. Zou, and G. L. Tian, "Real-coefficient FGG-FG-FFT for the combined field integral equation," Progress In Electromagnetics Research M, vol. 54, pp. 19-27, 2017.
 M. Frigo and S. G. Johnson, "The design and implementation of FFTW3," Proceedings of the IEEE, vol. 93, no. 2, pp. 216-231, 2005.
Jia-Ye Xie, (1,2) Guang Yu, (1) Li-Li Pang, (1) Wei-Bin Kong, (2,3) and Zhi-Xiang Huang (4)
(1) Industrial Center, Nanjing Institute of Technology, Nanjing 211167, China
(2) State Key Laboratory of Millimeter Waves, Nanjing 210096, China
(3) College of Information Engineering, Yancheng Institute of Technology, Yancheng 224051, China
(4) Key Laboratory of Intelligent Computing and Signal Processing, Ministry of Education, Anhui University, Hefei 230601, China
Correspondence should be addressed to Jia-Ye Xie; firstname.lastname@example.org
Received 27 April 2017; Accepted 17 August 2017; Published 28 September 2017.
Academic Editor: Angelo Liseno
Caption: Figure 1: A 2D representation of the obtaining projection coefficients.
Caption: Figure 2: A 2D representation of the difference between the far elements and the near elements. (a) A far element without coincident point; (b) a near element with coincident points.
Caption: Figure 3: Fitting Green's functions and accurate Green's function. (a) h = 0.1[lambda]; (b) h = 0.2[lambda].
Caption: Figure 4: The bistatic RCS curves of the PEC Sphere. (a) h = 0.1[lambda]; (b) h = 0.2[lambda].
Caption: Figure 5: The bistatic RCS curves of the PEC aircraft-like model.
Table 1: RMSEs of the real parts of fitting Green's functions. h 0.1[lambda] R' 0.002[lambda] 0.2[lambda] h/4 d [1.25h, 1.5h] 1.27E + 0 1.42E - 1 4.34E - 2 [1.5h, 1.75h] 8.10E - 1 7.65E - 2 1.52E - 2 [1.75h, 2h] 4.51E - 1 3.78E - 2 5.01E - 3 [2h, 2.25h] 2.20E - 1 1.74E - 2 2.49E - 3 [2.25h, 2.5h] 9.52E - 2 7.44E - 3 1.19E - 3 [2.5h, 2.75h] 3.48E - 2 2.74E - 3 6.70E - 4 [2.75h, 3h] 1.20E - 2 9.71E - 4 3.94E - 4 [3h, 3.25h] 3.25E - 3 3.23E - 4 2.31E - 4 h 0.2[lambda] R' 0.002[lambda] 0.2[lambda] h/4 d [1.25h, 1.5h] 2.04E + 0 9.69E - 2 2.64E - 2 [1.5h, 1.75h] 1.30E + 0 5.25E - 2 9.06E - 3 [1.75h, 2h] 7.24E - 1 2.64E - 2 3.45E - 3 [2h, 2.25h] 3.55E - 1 1.23E - 2 1.76E - 3 [2.25h, 2.5h] 1.56E - 1 5.38E - 3 1.03E - 3 [2.5h, 2.75h] 5.59E - 2 1.97E - 3 5.71E - 4 [2.75h, 3h] 2.01E - 2 7.84E - 4 2.84E - 4 [3h, 3.25h] 5.69E - 3 3.52E - 4 2.16E - 4 Table 2: Some related data for examples. Memory requirement (M) Ex h([lambda]) Method Near-field Coefficient Total A 0.1 [T] 236 488 1024 [O] 123 488 911 0.2 [T] 840 428 1364 [O] 345 428 869 B 0.2 [T] 1458 709 2502 [O] 607 709 1651 CPU time (s) Ex h([lambda]) Method RMSE Correction Per Total matrix iteration A 0.1 [T] 115 10.23 1270 0.060 [O] 73 10.12 1224 0.061 0.2 [T] 317 2.75 710 0.071 [O] 134 2.25 512 0.073 B 0.2 [T] 518 6.8 1541 0.089 [O] 229 6.1 1248 0.094
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||Research Article|
|Author:||Xie, Jia-Ye; Yu, Guang; Pang, Li-Li; Kong, Wei-Bin; Huang, Zhi-Xiang|
|Publication:||International Journal of Antennas and Propagation|
|Date:||Jan 1, 2017|
|Previous Article:||A Novel Ancient Coin-Like Fractal Multiband Antenna for Wireless Applications.|
|Next Article:||Experimental Results of Novel DoA Estimation Algorithms for Compact Reconfigurable Antennas.|