×

Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems. (English) Zbl 1017.65027

Summary: We consider the preconditioned iterative solution of large dense linear systems, where the coefficient matrix is a complex valued matrix arising from discretizing the integral equation of electromagnetic scattering. For some scattering structures this matrix can be poorly conditioned. The main purpose of this study is to evaluate the efficiency of a class of incomplete LU (ILU) factorization preconditioners for solving this type of matrices.
We solve the electromagnetic wave equations using the BiCG method with an ILU preconditioner in the context of a multilevel fast multipole algorithm (MLFMA). The novelty of this work is that the ILU preconditioner is constructed using the near part block diagonal submatrices generated from the MLFMA. Experimental results show that the ILU preconditioner reduces the number of BiCG iterations substantially, compared to the block diagonal preconditioner. The preconditioned iteration scheme also maintains the computational complexity of the MLFMA, and consequently reduces the total CPU time.

MSC:

65F10 Iterative numerical methods for linear systems
65N38 Boundary element methods for boundary value problems involving PDEs
78M15 Boundary element methods applied to problems in optics and electromagnetic theory
65Y20 Complexity and performance of numerical algorithms
65F35 Numerical computation of matrix norms, conditioning, scaling
78A45 Diffraction, scattering
35Q60 PDEs in connection with optics and electromagnetic theory

Software:

ILUT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0795.65014
[2] Alléon, G.; Benzi, M.; Giraud, L., Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics, Numer. Alg., 16, 1-15 (1997) · Zbl 0895.65017
[3] Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), SIAM: SIAM Philadelphia
[4] Carpentieri, B.; Duff, I. S.; Giraud, L., Sparse pattern selection strategies for robust Frobenius-norm minimization preconditioners in electromagnetism, Numer. Linear Algebra Appl., 7, 667-685 (2000) · Zbl 1051.65050
[5] B. Carpentieri, I.S. Duff, L. Giraud, Experiments with sparse preconditioning of dense problems from electromagnetic applications, Technical Report TR/PA/00/04, CERFACS, Toulouse, France, 2000; B. Carpentieri, I.S. Duff, L. Giraud, Experiments with sparse preconditioning of dense problems from electromagnetic applications, Technical Report TR/PA/00/04, CERFACS, Toulouse, France, 2000
[6] B. Carpentieri, I.S. Duff, M. Magolu monga Made, Sparse symmetric preconditioners for dense linear systems in electromagnetism, Technical Report TR/PA/01/35, CERFACS, Toulouse, France, 2001; B. Carpentieri, I.S. Duff, M. Magolu monga Made, Sparse symmetric preconditioners for dense linear systems in electromagnetism, Technical Report TR/PA/01/35, CERFACS, Toulouse, France, 2001
[7] Chen, K., On a class of preconditioning methods for the dense linear systems from boundary elements, SIAM J. Sci. Comput., 20, 2, 684-698 (1998) · Zbl 0924.65037
[8] D’Azevedo, E. F.; Forsyth, F. A.; Tang, W. P., Towards a cost effective ILU preconditioner with high level fill, BIT, 33, 1-25 (1990)
[9] Chew, W. C.; Jin, J. M.; Midielssen, E.; Song, J. M., Fast and Efficient Algorithms in Computational Electromagnetics (2001), Artech House: Artech House Boston
[10] Chow, E.; Saad, Y., Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 86, 387-414 (1997) · Zbl 0891.65028
[11] Coifman, R.; Rokhlin, V.; Wandzura, S., The fast multipole method for the wave equation: a pedestrian prescription, IEEE Antennas Propagat. Mag., 35, 3, 7-12 (1993)
[12] Darve, E., The fast multipole method: numerical implementation, J. Comput. Phys., 160, 195-240 (2000) · Zbl 0974.78012
[13] Greenbaum, A., Iterative Methods for Solving Linear Systems (1997), SIAM: SIAM Philadelphia · Zbl 0883.65022
[14] Kolundzija, B. M., Electromagnetic modeling of composite metallic and dielectric structures, IEEE Trans. Microwave Theory Tech., 47, 7, 1021-1032 (1999)
[15] Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Natl. Bur. Stand., 49, 33-53 (1952)
[16] J. Lee, J. Zhang, C. Lu, Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems, Technical Report No. 342-02, Department of Computer Science, University of Kentucky, Lexington, KY, 2002; J. Lee, J. Zhang, C. Lu, Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems, Technical Report No. 342-02, Department of Computer Science, University of Kentucky, Lexington, KY, 2002 · Zbl 1017.65027
[17] Lu, C. C.; Chew, W. C., A multilevel algorithm for solving a boundary integral equation of wave scattering, IEEE Trans. Micro. Opt. Tech. Lett., 7, 10, 466-470 (1994)
[18] Lu, C. C.; Chew, W. C., A coupled surface-volume integral equation approach for the calculation of electromagnetic scattering from composite metallic and material targets, IEEE Trans. Antennas Propagat., 48, 12, 1866-1868 (2000)
[19] Meijerink, J. A.; van der Vorst, H. A., An iterative solution method for linear systems of which the coefficient matrix is a symmetric \(M\)-matrix, Math. Comput., 31, 148-162 (1977) · Zbl 0349.65020
[20] J. Rahola, Experiments on iterative methods and the fast multipole method in electromagnetic scattering calculations, Technical Report TR/PA/98/49, CERFACS, Toulouse, France, 1998; J. Rahola, Experiments on iterative methods and the fast multipole method in electromagnetic scattering calculations, Technical Report TR/PA/98/49, CERFACS, Toulouse, France, 1998
[21] Rao, S. M.; Wilton, D. R.; Glisson, A. W., Electromagnetic scattering by surface of arbitrary shape, IEEE Trans. Antennas Propagat., AP-30, 3, 409-418 (1982)
[22] Rokhlin, V., Rapid solution of integral equations of scattering theory in two dimensions, J. Comput. Phys., 86, 2, 414-439 (1990) · Zbl 0686.65079
[23] Saad, Y., ILUT: a dual threshold incomplete LU factorization, Numer. Linear Algebra Appl., 1, 4, 387-402 (1994) · Zbl 0838.65026
[24] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing Company: PWS Publishing Company Boston · Zbl 1002.65042
[25] Sertel, K.; Volakis, J. L., Incomplete LU preconditioner for FMM implementation, Micro. Opt. Tech. Lett., 26, 7, 265-267 (2000)
[26] Shark, T. K.; Rao, S. M.; Djordievic, A. R., Electromagnetic scattering and radiation from finite microstrip structures, IEEE Trans. Micro. Opt. Tech., 38, 11, 1568-1575 (1990)
[27] Song, J. M.; Chew, W. C., Multilevel fast multipole algorithm for solving combined field integral equation of electromagnetic scattering, Micro. Opt. Tech. Lett., 10, 1, 14-19 (1995)
[28] Song, J. M.; Lu, C. C.; Chew, W. C., Multilevel fast multipole algorithm for electromagnetic scattering by large complex objects, IEEE Trans. Antennas Propagat., AP-45, 10, 1488-1493 (1997)
[29] Vaupel, T.; Hansen, V., Electrodynamic analysis of combined microstrip and coplanar/slotline structure with 3-D components based on a surface/volume integral equation approach, IEEE Trans. Microwave Theory Tech., 47, 9, 1150-1155 (1999)
[30] Vorobyev, Y. V., Method of Moments in Applied Mathematics (1965), Gordon and Breach Science: Gordon and Breach Science New York
[31] Wang, C. F.; Jin, J. M., A fast full-wave analysis of scattering and radiation from large finite arrays of microstrip antennas, IEEE Trans. Antennas Propagat., 46, 10, 1467-1474 (1998)
[32] Watts, J. W., A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation, Society of Petroleum Engineer J., 21, 345-353 (1981)
[33] Zhang, J., Preconditioned Krylov subspace methods for solving nonsymmetric matrices from CFD applications, Comput. Methods Appl. Mech. Engrg., 189, 3, 825-840 (2000) · Zbl 0991.76067
[34] Zhang, J., Sparse approximate inverse and multilevel block ILU preconditioning techniques for general sparse matrices, Appl. Numer. Math., 35, 67-86 (2000) · Zbl 0966.65043
[35] Zhang, J., A multilevel dual reordering strategy for robust incomplete LU factorization of indefinite matrices, SIAM J. Matrix Anal. Appl., 22, 3, 925-947 (2001) · Zbl 0993.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.