基于快速多极子方法的高效迭代方法及其工程应用
|
摘要
军用目标的隐身设计、反隐身技术研究,雷达系统设计与雷达目标识别等工程技术的最新发展,迫切需要对复杂目标电磁散射特性的精确快速求解。基于矩量法的快速多极子方法(FMM)和多层快速多极子方法(MLFMA)是积分方程的高效算法,其计算精度高,满足复杂目标散射特性分析的要求。然而,面对复杂的工程问题,还必须对多层快速多极子方法作进一步改进和优化。本文在快速多极子方法的基础上,进一步采取一系列有效的算法,加速矩阵方程的迭代求解。这些方法与一般的快速多极子方法相比,结果精度没有变差,但求解速度大大提高,更适合实际工程中对复杂结构目标RCS 计算的要求。
本文首先介绍快速多极子方法的基础——矩量法的关键技术,包括复杂目标的几何建模,基函数和权函数的选择等。接着详细了介绍快速多极子方法和多层快速多极子方法的基本原理和数值实现过程。然后,本文了总结使用MLFMA 程序计算目标RCS 过程中影响结果精度的关键因素,如几何剖分、电磁建模、积分方程类型的选择,等等,为工程用户提供技术规范,保证计算结果的精度。本文还完成了大量工程实例,证明了文中方法和程序的有效性和正确性。本文也指出工程应用中面临的挑战,从实际工程应用的方面对方法的改进提出了要求。
在此基础上,本文围绕加速迭代求解这个目标,从两个方向展开研究。(1) 在给定精度前提下减少迭代步数,采用适合于快速多极子方法的矩阵预条件技术,改善矩阵的条件数,加快迭代收敛。(2) 减少每次迭代过程的计算时间,本文采取了一种新的角谱数的计算准则,大大减少角谱空间中积分的计算量。以上两种方法都是严格的,不会降低快速多极子方法的精度。
本文所有实例的数值结果均与相应文献结果或已获验证的数值程序计算结果吻合良好,充分说明了这些算法的高效性和正确性。本文研究工作为电大尺寸复杂三维目标的矢量电磁散射高效分析提供了有效的手段,为越趋频繁的工程应用提供了强有力的支持。
With the development of the stealth and anti-stealth of the military targets, the radar system design and the radar recognition technology, the electromagnetic scattering property of the complex targets needs to be solved accurately and efficiently. The fast multipole method (FMM) and the Multilevel fast multipole algorithm (MLFMA) based on the method of moment (MOM) are the efficient algorithm for solving integral equation. For its high accuracy, it meets the analysis of the EM scattering property of the complex targets. The MLFMA must be further optimized to cope with the complex engineering.
Firstly, the differential equation methods, the integral equation methods and the hybrid methods used for analysis of scattering are reviewed. As the basis of FMM, the key techniques of MOM such as geometry modeling and the choice of basis/weight functions are discussed. The FMM and the MLFMA are studied in detail.
Secondly, the key points for RCS accuracy in MLFMA have been summarized. Including geometry modeling, electromagnetic modeling, the selection of integral equation, detailed technical requirement is provided to assure the accuracy. The challenges raise from the application are present, and advice for the optimization of the algorithm are list.
At last, several highly efficient iterative algorithms based on MLFMA are extensively studied. Such as use preconditioned conjugate gradient (PCG) algorithm to reduce the iterative steps, use modified multipole numbers method to reduce the computation of each step.
All numerical results in the paper agree well with the results in the references and those computed by confirmed numerical programs. It proves well their high efficiency and accuracy. The research work in this paper provides a useful means for fast analysis of scattering from complex 3D targets with large electrical size and gives strong support to engineering.
本文首先介绍快速多极子方法的基础——矩量法的关键技术,包括复杂目标的几何建模,基函数和权函数的选择等。接着详细了介绍快速多极子方法和多层快速多极子方法的基本原理和数值实现过程。然后,本文了总结使用MLFMA 程序计算目标RCS 过程中影响结果精度的关键因素,如几何剖分、电磁建模、积分方程类型的选择,等等,为工程用户提供技术规范,保证计算结果的精度。本文还完成了大量工程实例,证明了文中方法和程序的有效性和正确性。本文也指出工程应用中面临的挑战,从实际工程应用的方面对方法的改进提出了要求。
在此基础上,本文围绕加速迭代求解这个目标,从两个方向展开研究。(1) 在给定精度前提下减少迭代步数,采用适合于快速多极子方法的矩阵预条件技术,改善矩阵的条件数,加快迭代收敛。(2) 减少每次迭代过程的计算时间,本文采取了一种新的角谱数的计算准则,大大减少角谱空间中积分的计算量。以上两种方法都是严格的,不会降低快速多极子方法的精度。
本文所有实例的数值结果均与相应文献结果或已获验证的数值程序计算结果吻合良好,充分说明了这些算法的高效性和正确性。本文研究工作为电大尺寸复杂三维目标的矢量电磁散射高效分析提供了有效的手段,为越趋频繁的工程应用提供了强有力的支持。
With the development of the stealth and anti-stealth of the military targets, the radar system design and the radar recognition technology, the electromagnetic scattering property of the complex targets needs to be solved accurately and efficiently. The fast multipole method (FMM) and the Multilevel fast multipole algorithm (MLFMA) based on the method of moment (MOM) are the efficient algorithm for solving integral equation. For its high accuracy, it meets the analysis of the EM scattering property of the complex targets. The MLFMA must be further optimized to cope with the complex engineering.
Firstly, the differential equation methods, the integral equation methods and the hybrid methods used for analysis of scattering are reviewed. As the basis of FMM, the key techniques of MOM such as geometry modeling and the choice of basis/weight functions are discussed. The FMM and the MLFMA are studied in detail.
Secondly, the key points for RCS accuracy in MLFMA have been summarized. Including geometry modeling, electromagnetic modeling, the selection of integral equation, detailed technical requirement is provided to assure the accuracy. The challenges raise from the application are present, and advice for the optimization of the algorithm are list.
At last, several highly efficient iterative algorithms based on MLFMA are extensively studied. Such as use preconditioned conjugate gradient (PCG) algorithm to reduce the iterative steps, use modified multipole numbers method to reduce the computation of each step.
All numerical results in the paper agree well with the results in the references and those computed by confirmed numerical programs. It proves well their high efficiency and accuracy. The research work in this paper provides a useful means for fast analysis of scattering from complex 3D targets with large electrical size and gives strong support to engineering.
引文
[1] 聂在平,胡俊,姚海英,王浩刚。用于复杂目标三维矢量散射分析的快速多极子方法.电子学报,Vol. 27, No. 6, pp. 104-109, 1999
[2] J.J. Dongarra, F. Sullivan. The Top 10 Algorithms in 20th century, IEEE Computing in Science and Engineering, No.2, pp22-23, 2000
[3] V. Rokhlin. Rapid solution of integral equations of scattering theory in two dimensions. Journal of Computational physics, 1990, 86:414-439
[4] J.M. Song and W.C. Chew. Fast multipole method solution using parametric geometry. Microwave and Optical Technology Letters, 1994, 7(16):760-765
[5] C.C. Lu, W.C. Chew. Fast algorithm for solving hybrid integral equations. IEE PROCEEDINGS-H, 1993, 140(5):455-460
[6] C.C. Lu and W.C. Chew. Electromagnetic scattering from material coated PEC objects: a hybrid volume and surface integral approach. IEEE Antennas Propagation Symposium, 1999
[7] Cai-Cheng Lu and Weng Cho Chew. Fast far-field approximation for calculating the RCS of large objects. Microwave and Optical Technology Letters, 1995, 8(5):238-241
[8] W.C. Chew, Y.M. Wang, and L. Gurel. Recursive algorithm for wave-scattering solutions using windowed addition theorem. Journal of electromagnetic waves and applications, 1992, 6(11):1537-1560
[9] Robert D. Graglia, On the Numerical Integration of the Linear Shape Function Times the 3-D Green’s Function or its Gradient on a Plane Triangle, IEEE Trans on Antennas Progat, 1993, Vol.41, No.10: 1448-1455
[10] J.M. Song, C.C. Lu., W.C. Chew. Multilevel fast multipole algorithm for electromagnetic scattering by large complex bojects. IEEE Transaction on Antennas Propagation, 1997, 45(10):1488-1493
[11] J.M. Song, C.C. Lu, W.C. Chew and S.W. Lee. Introduction to Fast Illinois Solver Code (FISC). IEEE Antennas Propagation Symposium, 1997, 48-51
[12] J.M .Song, C.C. Lu, W.C. Chew, and S.W. Lee. Fast Illinois Solver Code (FISC), IEEE Transactions on Antennas and Propagation, 1998, 40(3):27-34
[13] J.M. Song and W.C. Chew. Multilevel fast-multipole algorithm for solving combined field integral equations of electromagnetic scattering. Microwave and Optical Tech. Letter, 1995, 10(10):14-19
[14] X.Q. Sheng, J.M. Jin, J.M. Song, etc. On the formulation of hybrid finite-element and boundary-integral methods for 3D scattering using multi-level fast multipole algorithm. IEEE Antennas Propagations
Symposium, 1998, 236-239
[15] Caicheng Lu and Wengcho Chew. A multilevel algorithm for solving a boundary integral equation of wave scattering. Microwave and Optical Technology Letters, 1994, 7(10):466-470
[16] S. Koc, J.M. Song, W.C. Chew. Error analysis for the multilevel fast multipole algorithm. IEEE Antennas propagation Symposium, 1998, 1758-1761
[17] J.M. Song and W.C. Chew. Requirements scaling properties in large scale computing. IEEE Antennas Propagation Symposium, 1998, 1518-1521
[18] Hu Jun, Nie Zaiping, Solution of Electromagnetic Scattering from Two-dimensional Conductor by using FMM with BiCG method, Chinese Journal of Electronics,Vol.6, No.4, pp.40-42,1997,10
[19] 王浩刚,聂在平。一种基于快速求解单站RCS 的新算法-基波激励法,计算物理学会第二届计算电磁学研讨会(SCEM’98), pp.74-77, 1998,7.
[20] 聂在平,胡俊。三维矢量电磁散射高效数值分析中新的迭代方法,电波科学学报. 1999 年, Vol.14, pp.99-102
[21] 王浩刚,聂在平。三维矢量散射积分方程中奇异性分析,电子学报, No.12,1999 No.3, 1999
[22] 胡俊。复杂目标矢量电磁散射的高效算法—快速多极子算法及其应用,博士论文,2000
[23] 王浩刚。电大尺寸含腔体复杂目标矢量电磁散射一体化精确建模与高效算法研究,博士论文,2001
[24] K.S. Yee. Numerical solution of initial boundary value problem involving Maxwell’s equations in isotropic media. IEEE Transactions on antennas and propagation, AP-14.4, pp. 302-307, 1966
[25] Jean-Pierre Berengeer. A perfectly matched layer for the absorption of electromagnetic waves. Journal of Computational Physics, 1994, 114:185-200
[26] R. F. Harrington. Field computation by Moment Methods, New York, Macmillan, 1968
[27] 周永祖著,聂在平,柳清伙译。《非均匀介质中的场与波》.电子工业出版社,1992 年
[28] Chew W. C., S. Barone, B. Anderson and C. Hennessy. Diffraction of axisymmetric waves in a borehole by bed boundary discontinuities. Geophysics, Vol. 49, No. 10, pp. 1586-1595, 1984
[29] Chew W. C. and B. Anderson, Propagation of electromagnetic waves through geological beds in a geophysical probing environment. Radio Science, Vol. 20, No. 3, pp. 611-621, 1985
[30] 李世智。《电磁散射与辐射问题的矩量法》,电子工业出版社, 1985。
[31] J. M. Song, W. C. Chew. Moment method solution using parametric geometry. Journal of Electromagnetic Wave and Applications, 1995, 9(1/2):71-83
[32] S.M. Rao, D.R. Wilton, and A.W. Glisson. “Electromagnetic scattering by surfaces of arbitrary shape”, IEEE Trans. Antennas Propagat. , Vol.30, pp.409-418, May, 1982
[33] 陈维桓,微分几何初步,北京:北京大学出版社, 1990。
[34] 金建铭著,王建国译,葛德彪校。电磁场有限元方法,西安:西安电子科技大学出版社,1998。
[35] 李正良,《矩阵理论及应用》,高等教育出版社, 1996。
[36] Yousef Saad. Iterative Methods for Sparse Linear Systems, Second Edition, 2000.
[37] Bruno CARPENTIERI. Sparse Preconditioners for Dense Linear Systems From Electromagnetic Applications. PhD Thesis, 2002.
[38] K.F. Tsang, R.S. Chen, Mo Lei, Edward K.N. Yung. Application of the Precdonditioned Conjugate-Gradient Algorithm to the Integral Equations for Microwave Circuits. Microwave and Optical Technology Letters, Vol.34, No.4, pp.266-269,August 20,2002.
[39] M. Carr, M. Bleszynski, and J.L. Volakis. A Near-field Preconditioner and its Performance in Conjunction with the BiCGstab(ell) Solver. IEEE Antennas and Propagation Magazine, Vol.46, No.2, April 2004.
[40] 徐士良, FORTRAN 常用算法程序集,第二版,清华大学出版社, 1995。
[41] W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery. Numerical Recipes in C, The Art of Scientific Computing, Second Edition, Cambridge University Press, 1992.
[42] J.M. Song, C.C. Lu., W.C. Chew, S.W. Lee,Fast Illinois Solver Code (FISC), IEEE Antennas and Propagation Magazine, Vol.40, No.3, June 1998.
[43] W.C. Chew, J.M. Jin, Eric Michielssen, J.M. Song. Fast and Efficient Algorithms in Computational Electromagnetics. Artech House, 2001.
[44] Alex C. Woo, Helen T. G. Wang, Michael J. Schuh, Michael L. Sanders. Benchmark radar targets for the validation of computational electromagnetics programs. IEEE Antennas and Propagation Magazine, 1993, 35(1): 84-89
[45] R. Coifman, V. Rokhlin, and S. Wandzura. The fast multipole method for the wave equation: A pedestrian prescription, IEEE Antennas Propagat. Mag., vol. 35, pp. 7–12, June 1993.
[46] Robert L. Wagner and Weng Cho Chew. A ray-propagation fast multipole algorithm. Micro. Opt. Tech. Lett., vol. 7, no. 10, pp. 435-438, July 1994.
[2] J.J. Dongarra, F. Sullivan. The Top 10 Algorithms in 20th century, IEEE Computing in Science and Engineering, No.2, pp22-23, 2000
[3] V. Rokhlin. Rapid solution of integral equations of scattering theory in two dimensions. Journal of Computational physics, 1990, 86:414-439
[4] J.M. Song and W.C. Chew. Fast multipole method solution using parametric geometry. Microwave and Optical Technology Letters, 1994, 7(16):760-765
[5] C.C. Lu, W.C. Chew. Fast algorithm for solving hybrid integral equations. IEE PROCEEDINGS-H, 1993, 140(5):455-460
[6] C.C. Lu and W.C. Chew. Electromagnetic scattering from material coated PEC objects: a hybrid volume and surface integral approach. IEEE Antennas Propagation Symposium, 1999
[7] Cai-Cheng Lu and Weng Cho Chew. Fast far-field approximation for calculating the RCS of large objects. Microwave and Optical Technology Letters, 1995, 8(5):238-241
[8] W.C. Chew, Y.M. Wang, and L. Gurel. Recursive algorithm for wave-scattering solutions using windowed addition theorem. Journal of electromagnetic waves and applications, 1992, 6(11):1537-1560
[9] Robert D. Graglia, On the Numerical Integration of the Linear Shape Function Times the 3-D Green’s Function or its Gradient on a Plane Triangle, IEEE Trans on Antennas Progat, 1993, Vol.41, No.10: 1448-1455
[10] J.M. Song, C.C. Lu., W.C. Chew. Multilevel fast multipole algorithm for electromagnetic scattering by large complex bojects. IEEE Transaction on Antennas Propagation, 1997, 45(10):1488-1493
[11] J.M. Song, C.C. Lu, W.C. Chew and S.W. Lee. Introduction to Fast Illinois Solver Code (FISC). IEEE Antennas Propagation Symposium, 1997, 48-51
[12] J.M .Song, C.C. Lu, W.C. Chew, and S.W. Lee. Fast Illinois Solver Code (FISC), IEEE Transactions on Antennas and Propagation, 1998, 40(3):27-34
[13] J.M. Song and W.C. Chew. Multilevel fast-multipole algorithm for solving combined field integral equations of electromagnetic scattering. Microwave and Optical Tech. Letter, 1995, 10(10):14-19
[14] X.Q. Sheng, J.M. Jin, J.M. Song, etc. On the formulation of hybrid finite-element and boundary-integral methods for 3D scattering using multi-level fast multipole algorithm. IEEE Antennas Propagations
Symposium, 1998, 236-239
[15] Caicheng Lu and Wengcho Chew. A multilevel algorithm for solving a boundary integral equation of wave scattering. Microwave and Optical Technology Letters, 1994, 7(10):466-470
[16] S. Koc, J.M. Song, W.C. Chew. Error analysis for the multilevel fast multipole algorithm. IEEE Antennas propagation Symposium, 1998, 1758-1761
[17] J.M. Song and W.C. Chew. Requirements scaling properties in large scale computing. IEEE Antennas Propagation Symposium, 1998, 1518-1521
[18] Hu Jun, Nie Zaiping, Solution of Electromagnetic Scattering from Two-dimensional Conductor by using FMM with BiCG method, Chinese Journal of Electronics,Vol.6, No.4, pp.40-42,1997,10
[19] 王浩刚,聂在平。一种基于快速求解单站RCS 的新算法-基波激励法,计算物理学会第二届计算电磁学研讨会(SCEM’98), pp.74-77, 1998,7.
[20] 聂在平,胡俊。三维矢量电磁散射高效数值分析中新的迭代方法,电波科学学报. 1999 年, Vol.14, pp.99-102
[21] 王浩刚,聂在平。三维矢量散射积分方程中奇异性分析,电子学报, No.12,1999 No.3, 1999
[22] 胡俊。复杂目标矢量电磁散射的高效算法—快速多极子算法及其应用,博士论文,2000
[23] 王浩刚。电大尺寸含腔体复杂目标矢量电磁散射一体化精确建模与高效算法研究,博士论文,2001
[24] K.S. Yee. Numerical solution of initial boundary value problem involving Maxwell’s equations in isotropic media. IEEE Transactions on antennas and propagation, AP-14.4, pp. 302-307, 1966
[25] Jean-Pierre Berengeer. A perfectly matched layer for the absorption of electromagnetic waves. Journal of Computational Physics, 1994, 114:185-200
[26] R. F. Harrington. Field computation by Moment Methods, New York, Macmillan, 1968
[27] 周永祖著,聂在平,柳清伙译。《非均匀介质中的场与波》.电子工业出版社,1992 年
[28] Chew W. C., S. Barone, B. Anderson and C. Hennessy. Diffraction of axisymmetric waves in a borehole by bed boundary discontinuities. Geophysics, Vol. 49, No. 10, pp. 1586-1595, 1984
[29] Chew W. C. and B. Anderson, Propagation of electromagnetic waves through geological beds in a geophysical probing environment. Radio Science, Vol. 20, No. 3, pp. 611-621, 1985
[30] 李世智。《电磁散射与辐射问题的矩量法》,电子工业出版社, 1985。
[31] J. M. Song, W. C. Chew. Moment method solution using parametric geometry. Journal of Electromagnetic Wave and Applications, 1995, 9(1/2):71-83
[32] S.M. Rao, D.R. Wilton, and A.W. Glisson. “Electromagnetic scattering by surfaces of arbitrary shape”, IEEE Trans. Antennas Propagat. , Vol.30, pp.409-418, May, 1982
[33] 陈维桓,微分几何初步,北京:北京大学出版社, 1990。
[34] 金建铭著,王建国译,葛德彪校。电磁场有限元方法,西安:西安电子科技大学出版社,1998。
[35] 李正良,《矩阵理论及应用》,高等教育出版社, 1996。
[36] Yousef Saad. Iterative Methods for Sparse Linear Systems, Second Edition, 2000.
[37] Bruno CARPENTIERI. Sparse Preconditioners for Dense Linear Systems From Electromagnetic Applications. PhD Thesis, 2002.
[38] K.F. Tsang, R.S. Chen, Mo Lei, Edward K.N. Yung. Application of the Precdonditioned Conjugate-Gradient Algorithm to the Integral Equations for Microwave Circuits. Microwave and Optical Technology Letters, Vol.34, No.4, pp.266-269,August 20,2002.
[39] M. Carr, M. Bleszynski, and J.L. Volakis. A Near-field Preconditioner and its Performance in Conjunction with the BiCGstab(ell) Solver. IEEE Antennas and Propagation Magazine, Vol.46, No.2, April 2004.
[40] 徐士良, FORTRAN 常用算法程序集,第二版,清华大学出版社, 1995。
[41] W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery. Numerical Recipes in C, The Art of Scientific Computing, Second Edition, Cambridge University Press, 1992.
[42] J.M. Song, C.C. Lu., W.C. Chew, S.W. Lee,Fast Illinois Solver Code (FISC), IEEE Antennas and Propagation Magazine, Vol.40, No.3, June 1998.
[43] W.C. Chew, J.M. Jin, Eric Michielssen, J.M. Song. Fast and Efficient Algorithms in Computational Electromagnetics. Artech House, 2001.
[44] Alex C. Woo, Helen T. G. Wang, Michael J. Schuh, Michael L. Sanders. Benchmark radar targets for the validation of computational electromagnetics programs. IEEE Antennas and Propagation Magazine, 1993, 35(1): 84-89
[45] R. Coifman, V. Rokhlin, and S. Wandzura. The fast multipole method for the wave equation: A pedestrian prescription, IEEE Antennas Propagat. Mag., vol. 35, pp. 7–12, June 1993.
[46] Robert L. Wagner and Weng Cho Chew. A ray-propagation fast multipole algorithm. Micro. Opt. Tech. Lett., vol. 7, no. 10, pp. 435-438, July 1994.