volume | PIER Journals

Abstract

In this paper, we consider a novel class of Krylov projection methods computed from the Lanczos biconjugate A-Orthonormalization procedure for the solution of dense complex non-Hermitian linear systems arising from the Method of Moments discretization of Maxwell's equations. We report on experiments on a set of model problems representative of realistic radar-cross section calculations to show their competitiveness with other popular Krylov solvers, especially when memory is a concern. The results presented in this study will contribute to assess the potential of iterative Krylov methods for solving electromagnetic scattering problems from large structures enriching the database of this technology.

1. Alleon, G., S. Amram, N. Durante, P. Homsi, D. Pogarieloff, and C. Farhat, "Massively parallel processing boosts the solution of industrial electromagnetic problems: High performance out-of-core solution of complex dense systems," Proceedings of the Eighth SIAM Conference on Parallel Computing, M. Heath, V. Torczon, G. Astfalk, P. E. Bjrstad, A. H. Karp, C. H. Koebel, V. Kumar, R. F. Lucas, L. T. Watson, and D. E. Womble (eds.), SIAM Book, Philadelphia, Conference held in Minneapolis, Minnesota, USA, 1997.

2. Bendali, A., "Approximation par elements finis de surface de problemes de diffraction des ondes electro-magnetiques,", Ph.D. thesis, Universite Paris VI, 1984.

3. Bilotti, F. and C. Vegni, "MoM entire domain basis functions for convex polygonal patches," Journal of Electromagnetic Waves and Applications, Vol. 17, No. 11, 1519-1538, 2003.
doi:10.1163/156939303772681398

4. Carpentieri, B., I. S. Duff, and L. Giraud, "Sparse pattern selection strategies for robust Frobenius-norm minimization preconditioners in electromagnetism," Numerical Linear Algebra with Applications, Vol. 7, No. 7-8, 667-685, 2000.
doi:10.1002/1099-1506(200010/12)7:7/8<667::AID-NLA218>3.0.CO;2-X

5. Carpentieri, B., I. S. Duff, L. Giraud, and M. Magolu monga Made, "Sparse symmetric preconditioners for dense linear systems in electromagnetism," Numerical Linear Algebra with Applications, Vol. 11, 753-771, 2004.
doi:10.1002/nla.345

6. Carpentieri, B., I. S. Duff, L. Giraud, and G. Sylvand, "Combining fast multipole techniques and an approximate inverse preconditioner for large electromagnetism calculations," SIAM J. Scientific Computing, Vol. 27, No. 3, 774-792, 2005.
doi:10.1137/040603917

7. Chew, W. C. and Y. M. Wang, "A recursive T-matrix approach for the solution of electromagnetic scattering by many spheres," IEEE Transactions on Antennas and Propagation, Vol. 41, No. 12, 1633-1639, 1993.
doi:10.1109/8.273306

8. Chew, W. C. and K. F. Warnick, "On the spectrum of the electric field integral equation and the convergence of the moment method," Int. J. Numerical Methods in Engineering, Vol. 51, 475-489, 2001.

9. Danesfahani, R., S. Hatamzadeh-Varmazyar, E. Babolian, and Z. Masouri, "Applying Shannon wavelet basis functions to the Method of Moments for evaluating the Radar Cross Section of the conducting and resistive surfaces," Progress In Electromagnetics Research B, Vol. 8, 257-292, 2008.
doi:10.2528/PIERB08062601

10. Darve, E., "The fast multipole method (i): Error analysis and asymptotic complexity," SIAM J. Numerical Analysis, Vol. 38, No. 1, 98-128, 2000.
doi:10.1137/S0036142999330379

11. Dembart, B. and M. A. Epton, "A 3D fast multipole method for electromagnetics with multiple levels,", Tech. Rep. ISSTECH-97-004, The Boeing Company, Seattle, WA, 1994.

12. Dongarra, J. J., I. S. Duff, D. C. Sorensen, and H. A. Van Der Vorst, Numerical Linear Algebra for High-performance Computers, Software, Environments, and Tools, Vol. 7, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998.

13. Durdos, R., "Krylov solvers for large symmetric dense complex linear systems in electromagnetism: Some numerical experiments,", Working Notes WN/PA/02/97, CERFACS, Toulouse, France, 2002.

14. Ergul, O. and L. Gurel, "Fast and accurate solutions of extremely large integral-equation problems discretized with tens of millions of unknowns," Electron. Lett., Vol. 43, No. 9, 499-500, 2007.
doi:10.1049/el:20070639

15. Ergul, O. and L. Gurel, "Efficient parallelization of the multilevel fast multipole algorithm for the solution of large-scale scattering problems," IEEE Transactions on Antennas and Propagation, Vol. 56, No. 8, 2335-2345, 2008.
doi:10.1109/TAP.2008.926757

16. Essid, C., M. B. B. Salah, K. Kochlef, A. Samet, and A. B. Kouki, "Spatial-spectral formulation of method of moment for rigorous analysis of microstrip structures," Progress In Electromagnetics Research Letters, Vol. 6, 17-26, 2009.
doi:10.2528/PIERL08112706

17. Barrett, R., et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, 1995.

18. Fan, Z., D.-Z. Ding, and R.-S. Chen, "The efficient analysis of electromagnetic scattering from composite structures using hybrid CFIE-IEFIE," Progress In Electromagnetics Research B, Vol. 10, 131-143, 2008.
doi:10.2528/PIERB08091606

19. Freund, R. W., "A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems," SIAM J. Scientific Computing, Vol. 14, No. 2, 470-482, 1993.
doi:10.1137/0914029

20. Freund, R. W. and N. M. Nachtigal, "QMR: A quasi-minimal residual method for non-Hermitian linear systems," Numerische Mathematik, Vol. 60, No. 3, 315-339, 1991.
doi:10.1007/BF01385726

21. Freund, R. W. and N. M. Nachtigal, "An implementation of the QMR method based on coupled two-term recurrences," SIAM J. Scientific Computing, Vol. 15, No. 2, 313-337, 1994.
doi:10.1137/0915022

22. Freund, R. W., "Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices," SIAM J. Sci. Stat. Comput., Vol. 13, No. 1, 425-448, 1992.
doi:10.1137/0913023

23. Gan, H. and W. C. Chew, "A discrete BiCG-FFT algorithm for solving 3-D inhomogeneous scatterer problems," Journal of Electromagnetic Waves and Applications, Vol. 9, No. 10, 1339-1357, 1995.

24. Gibson, W. C., The Method of Moments in Electromagnetics, Chapman & Hall/CRC, Boca Raton, FL, 2008.

25. Greenbaum, A., Iterative Methods for Solving Linear Systems, Vol. 17, Frontiers in Applied Mathematics, SIAM, 1997.

26. Greengard, L. and V. Rokhlin, "A fast algorithm for particle simulations," Journal of Computational Physics, Vol. 73, 325-348, 1987.
doi:10.1016/0021-9991(87)90140-9

27. Hassani, H. R. and M. Jahanbakht, "Method of Moment analysis of finite phased array of aperture coupled circular microstrip patch antennas," Progress In Electromagnetics Research B, Vol. 4, 197-210, 2008.
doi:10.2528/PIERB08010602

28. Ipsen, I. C. F. and C. D. Meyer, "The idea behind Krylov methods,", Tech. Rep. CRSC-TR97-3, NCSU Center for Research in Scientific Computation-To Appear in American Mathematical Monthly, Jan. 31, 1997.

29. Jing, Y.-F., T.-Z. Huang, Y. Zhang, L. Li, G.-H. Cheng, Z.-G. Ren, Y. Duan, T. Sogabe, and B. Carpentieri, "Lanczos-type variants of the COCR method for complex nonsymmetric linear systems," Journal of Computational Physics, Vol. 228, No. 17, 6376-6394, 2009.
doi:10.1016/j.jcp.2009.05.022

30. Lee, J., C.-C. Lu, and J. Zhang, "Sparse inverse preconditioning of multilevel fast multipole algorithm for hybrid integral equations in electromagnetics,", Tech. Rep. 363-02, Department of Computer Science, University of Kentucky, KY, 2002.

31. Lee, J., C.-C. Lu, and J. Zhang, "Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems," J. Comp. Phys., Vol. 185, 158-175, 2003.
doi:10.1016/S0021-9991(02)00052-9

32. Lee, J., C.-C. Lu, and J. Zhang, "Sparse inverse preconditioning of multilevel fast multipole algorithm for hybrid integral equations in electromagnetics," IEEE Transactions on Antennas and Propagation, Vol. 52, No. 9, 2277-2287, 2004.
doi:10.1109/TAP.2004.834084

33. Li, J. Y., L. W. Li, and Y. B. Gan, "Method of Moments analysis of waveguide slot antennas using the EFIE," Journal of Electromagnetic Waves and Applications, Vol. 19, No. 13, 1729-1748, 2005.
doi:10.1163/156939305775696810

34. Lin, J. H. and W. C. Chew, "BiCG-FFT T-matrix method for solving for the scattering solution from inhomogeneous bodies," IEEE Trans. Microwave Theory Tech..

35. Malas, T., O. Ergul, and L. Gurel, "Sequential and parallel preconditioners for large-scale integral-equation problems," Computational Electromagnetics Workshop, 35-43, Izmir, Turkey, Aug. 30-31, 2007.

36. Malas, T. and L. Gurel, "Incomplete LU preconditioning with multilevel fast multipole algorithm for electromagnetic scattering," SIAM J. Scientific Computing, Vol. 29, No. 4, 1476-1494, 2007.
doi:10.1137/060659107

37. Mittra, R. and K. Du, "Characteristic basis function method for iteration-free solution of large method of moments problems," Progress In Electromagnetics Research B, Vol. 6, 307-336, 2008.
doi:10.2528/PIERB08031206

38. Nilsson, M., "Iterative solution of Maxwell's equations in frequency domain,", Master's thesis, Uppsala University Department of Information Technology.

39. Rahola, J. and S. Tissari, "Iterative solution of dense linear systems arising from the electrostatic integral equation in MEG," Physics in Medicine and Biology, Vol. 47, No. 6, 961-975, 2002.

40. Rao, S. M., D. R. Wilton, and A. W. Glisson, "Electromagnetic scattering by surfaces of arbitrary shape," IEEE Trans. Antennas Propagat., Vol. 30, 409-418, 1982.
doi:10.1109/TAP.1982.1142818

41. Saad, Y., "A flexible inner-outer preconditioned GMRES algorithm," SIAM J. Scientific and Statistical Computing, Vol. 14, 461-469, 1993.
doi:10.1137/0914028

42. Saad, Y., Iterative Methods for Sparse Linear Systems, PWS Publishing, 1996.

43. Saad, Y. and M. H. Schultz, "GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems," SIAM J. Scientific and Statistical Computing, Vol. 7, 856-869, 1986.

44. Samant, A. R., E. Michielssen, and P. Saylor, "Approximate inverse based preconditioners for 2D dense matrix problems,", Tech. Rep. CCEM-11-96, University of Illinois, 1996.

45. Sertel, K. and J. L. Volakis, "Incomplete LU preconditioner for FMM implementation," Micro. Opt. Tech. Lett., Vol. 26, No. 7, 265-267, 2000.
doi:10.1002/1098-2760(20000820)26:4<265::AID-MOP18>3.0.CO;2-O

46. Sleijpen, G. L. G. and D. R. Fokkema, "BiCGstab(ell) for linear equations involving unsymmetric matrices with complex spectrum," ETNA, Vol. 1, 11-32, 1993.

47. Sogabe, T., "Extensions of the conjugate residual method,", Ph.D. thesis, University of Tokyo, 2006.

48. Sogabe, T., M. Sugihara, and S.-L. Zhang, "An extension of the conjugate residual method to nonsymmetric linear systems," J. Comput. Appl. Math., Vol. 226, 103-113, 2009.
doi:10.1016/j.cam.2008.05.018

49. Song, J. M. and W. C. Chew, "The fast illinois solver code: Requirements and scaling properties," IEEE Computational Science and Engineering, Vol. 5, No. 3, 19-23, 1998.
doi:10.1109/99.714589

50. Song, J. M., C.-C. Lu, and W. C. Chew, "Multilevel fast multipole algorithm for electromagnetic scattering by large complex objects," IEEE Transactions on Antennas and Propagation, Vol. 45, No. 10, 1488-1493, 1997.
doi:10.1109/8.633855

51. Song, J. M., C. C. Lu, W. C. Chew, and S. W. Lee, "Fast illinois solver code (FISC)," IEEE Antennas and Propagation Magazine, Vol. 40, No. 3, 27-34, 1998.
doi:10.1109/74.706067

52. Sonneveld, P., "CGS, a fast Lanczos-type solver for nonsymmetric linear systems," SIAM J. Scientific and Statistical Computing, Vol. 10, 36-52, 1989.

53. Su, D. Y., D.-M. Fu, and D. Yu, "Genetic algorithms and method of moments for the design of PIFAs," Progress In Electromagnetics Research Letters, Vol. 1, 9-18, 2008.
doi:10.2528/PIERL07110603

54. Sylvand, G., "La methode multipole rapide en electromagnetisme: Performances, parallelisation, applications,", Ph.D. thesis, Ecole Nationale des Ponts et Chaussees, 2002.

55. Sylvand, G., "Complex industrial computations in electromagnetism using the fast multipole method," Proceedings of Waves 2003, P. Joly, P. Neittaanmdki, G. C. Cohen, E. Heikkola (eds.), Mathematical and Numerical Aspects of Wave Propagation, 657-662, Springer, 2003.

56. Van Der Vorst, H. A., "Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems," SIAM J. Scientific and Statistical Computing, Vol. 13, 631-644, 1992.

Dr. Yan-Fei Jing

Dr. Bruno Carpentieri

Dr. Ting-Zhu Huang