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. Google Scholar

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

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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.. Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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

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. Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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. Google Scholar

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

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 Google Scholar

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 Google Scholar

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 Google Scholar

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 Google Scholar

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

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 Google Scholar

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

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. Google Scholar

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. Google Scholar

Dr. Yan-Fei Jing

Dr. Bruno Carpentieri

Dr. Ting-Zhu Huang