Lanczos-type variants of the COCR method for complex nonsymmetric linear systems. (English) Zbl 1173.65316
Summary: Motivated by the celebrated extending applications of the well-established Complex Biconjugate Gradient (CBiCG) method to deal with large three-dimensional electromagnetic scattering problems by M. D. Pocock and S. P. Walker [IEEE Trans. Antennas Propagat. 45, No. 1, 140–146 (1997)], three Lanczos-type variants of the recently introduced Conjugate \(A\)-Orthogonal Conjugate Residual (COCR) method by T. Sogabe and S.-L. Zhang [J. Comput. Appl. Math. 199, No. 2, 297–303 (2007; Zbl 1108.65028)] are explored for the solution of complex nonsymmetric linear systems. The first two can be respectively considered as mathematically equivalent but numerically improved popularizing versions of the BiCR and CRS methods for complex systems presented in T. Sogabe’s Ph.D. Dissertation [Extensions of the conjugate residual method, University of Tokyo (2006)]. And the last one is somewhat new and is a stabilized and more smoothly converging variant of the first two in some circumstances. The presented algorithms are with the hope of obtaining smoother and, hopefully, faster convergence behavior in comparison with the CBiCG method as well as its two corresponding variants. This motivation is demonstrated by numerical experiments performed on some selective matrices borrowed from the sparse matrix collection of the University of Florida by Davis.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
Citations:
Zbl 1108.65028References:
| [1] | Pocock, M. D.; Walker, S. P., The complex bi-conjugate gradient solver applied to large electromagnetic scattering problems, computational costs, and cost scalings, IEEE Trans. Antennas Propagat., 45, 140-146 (1997) |
| [2] | Sogabe, T.; Zhang, S.-L., A COCR method for solving complex symmetric linear systems, J. Comput. Appl. Math., 199, 297-303 (2007) · Zbl 1108.65028 |
| [3] | Dongarra, J.; Sullivan, F., Guest editors’ introduction to the top 10 algorithms, Comput. Sci. Eng., 2, 1, 22-23 (2000) |
| [4] | Hestenes, M. R.; Stiefel, E. L., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bureau Standards, 49, 409-436 (1952) · Zbl 0048.09901 |
| [5] | Lanczos, C., Solution of systems of linear equations by minized itertions, J. Res. Nat. Bureau Standards, 49, 33-53 (1952) |
| [6] | Brezinski, C., Padé Type Approximation and General Orthogonal Polynomials (1980), Birkhäuser-Verlag: Birkhäuser-Verlag Basel/Boston/Stuttgart · Zbl 0418.41012 |
| [7] | Simoncini, V.; Szyld, D. B., Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14, 1-59 (2007) · Zbl 1199.65112 |
| [8] | Fletcher, R., Conjugate Gradient Methods for Indefinite Systems. Conjugate Gradient Methods for Indefinite Systems, Lecture Notes in Mathematics, vol. 506 (1976), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York, pp. 73-89 · Zbl 0326.65033 |
| [9] | D.A.H. Jacobs, The Exploitation of Sparsity by Iterative Methods, Sparse Matrices and their Uses, I.S. Duff, Springer, 1981, pp. 191-222.; D.A.H. Jacobs, The Exploitation of Sparsity by Iterative Methods, Sparse Matrices and their Uses, I.S. Duff, Springer, 1981, pp. 191-222. · Zbl 0469.65016 |
| [10] | Jacobs, D. A.H., A generalization of the conjugate gradient method to solve complex systems, IMA J. Numer. Anal., 6, 447-452 (1986) · Zbl 0614.65028 |
| [11] | Sarkar, T. K., On the application of the generalized biconjugate gradient method, J. Electromagnet. Waves Appl., 1, 223-242 (1987) |
| [12] | Markham, G., Conjugate gradient type methods for indefinite, asymmetric, and complex systems, IMA J. Numer. Anal., 10, 155-170 (1990) · Zbl 0702.65032 |
| [13] | Smith, C. F.; Peterson, A. F.; Mittra, R., The biconjugate gradient method for electromagnetic scatterings, IEEE Trans. Antennas Propagat., 38, 938-940 (1990) |
| [14] | Joly, P.; Meurant, G., Complex conjugate gradient methods, Numer. Algo., 4, 379-406 (1993) · Zbl 0780.65021 |
| [15] | P. Joly, Méthode de gradient conjugué, Publications du Laboratoire d’Analyse Numérique Université Pierre et Marie Curie, Paris, 1984.; P. Joly, Méthode de gradient conjugué, Publications du Laboratoire d’Analyse Numérique Université Pierre et Marie Curie, Paris, 1984. |
| [16] | Sonneveld, P., CGS a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10, 36-52 (1989) · Zbl 0666.65029 |
| [17] | M. Clemens, T. Weiland, Iterative methods for the solution of very large complex-symmetric linear systems of equations in electromagnetics, in: T.A. Manteuffel, S.F. McCormick (Eds.), Eleventh Copper Mountain Conference on Iterative Methods, Part 2, 1996.; M. Clemens, T. Weiland, Iterative methods for the solution of very large complex-symmetric linear systems of equations in electromagnetics, in: T.A. Manteuffel, S.F. McCormick (Eds.), Eleventh Copper Mountain Conference on Iterative Methods, Part 2, 1996. |
| [18] | van der Vorst, H. A.; Melissen, J. B.M., A Petrov-Galerkin type method for solving \(Ax = b\), where \(A\) is symmetric complex, IEEE Trans. Mag., 26, 706-708 (1990) |
| [19] | Cullum, J.; Kerner, W.; Willoughby, R. A., A generalized nonsymmetric Lanczos procedure, Comput. Phys. Commu., 53, 19-48 (1989) · Zbl 0798.65050 |
| [20] | Cullum, J.; Willoughby, R. A., Lanczos Algorithms for Large Symmetric Eigenvalue Computations. Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Classics in Applied Mathematics, vol. 41 (1985), Birkhaüser: Birkhaüser Basel, vol. 1, Theory, vol. 2, Programs, vol. 1 reprinted by SIAM, Philadelphia, PA, 2002 · Zbl 0574.65028 |
| [21] | Clemens, M.; Weiland, T., Comparison of Krylov-type methods for complex linear systems applied to high-voltage problems, IEEE Trans. Mag., 5, 3335-3338 (1998) |
| [22] | Liang Li, Ting-Zhu Huang, Yan-Fei Jing, Application of the incomplete Cholesky factorization preconditioned conjugated orthogonal conjugate gradient algorithm to the vector FEM for 3-D electromagnetic scattering problems, Comput. Phys. Commun., submitted for publication.; Liang Li, Ting-Zhu Huang, Yan-Fei Jing, Application of the incomplete Cholesky factorization preconditioned conjugated orthogonal conjugate gradient algorithm to the vector FEM for 3-D electromagnetic scattering problems, Comput. Phys. Commun., submitted for publication. · Zbl 1205.78059 |
| [23] | Weiss, R., Parameter-Free Iterative Linear Solvers. Parameter-Free Iterative Linear Solvers, Mathematical Research, vol. 97 (1996), Akademie Verlag: Akademie Verlag Berlin · Zbl 0858.65031 |
| [24] | R. Weiss, Convergence behavior of generalized conjugate gradient method, Ph.D. Dissertation, University of Karlsruhe, 1990.; R. Weiss, Convergence behavior of generalized conjugate gradient method, Ph.D. Dissertation, University of Karlsruhe, 1990. · Zbl 0738.90074 |
| [25] | Weiss, R., Properties of generalized conjugate gradient methods, J. Numer. Linear Algebra Appl., 1, 45-63 (1994) · Zbl 0816.65013 |
| [26] | Saad, Y., Iterative Methods for Sparse Linear Systems (1996), The PWS Publishing Company: The PWS Publishing Company Boston, SIAM, Philadelphia, PA, 2003 · Zbl 1002.65042 |
| [27] | Gutknecht, Martin H.; Rozloz˘ník, Miroslav, A framework for generalized conjugate gradient methods – with special emphasis on contributions by Rűdiger Weiss, Appl. Numer. Math., 41, 7-22 (2002) · Zbl 0996.65034 |
| [28] | W. Schönauer, The efficient solution of large linear systems, resulting from the fdm for 3-d PDE’s, on vector computers, in: Proceedings of the 1st International colloquium on vector and parallel computing in Scientific Applications, Paris, March 1983, 1983.; W. Schönauer, The efficient solution of large linear systems, resulting from the fdm for 3-d PDE’s, on vector computers, in: Proceedings of the 1st International colloquium on vector and parallel computing in Scientific Applications, Paris, March 1983, 1983. |
| [29] | B. Hendrickson, R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, Technical Report SAND92-1460, UC-405, Sandia National Laboratories, Albuquerque, NM, 1992.; B. Hendrickson, R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, Technical Report SAND92-1460, UC-405, Sandia National Laboratories, Albuquerque, NM, 1992. · Zbl 0816.68093 |
| [30] | Brezinski, C.; Redivo-Zaglia, M., Hybrid procedures for solving systems of linear equations, Numer. Math., 67, 1-19 (1994) · Zbl 0797.65023 |
| [31] | Zhou, L.; Walker, H. F., Residual smoothing techniques for iterative methods, SIAM J. Sci. Comput., 15, 297-312 (1994) · Zbl 0802.65041 |
| [32] | R. Weiss, A theoretical overview of Krylov subspace methods, in: W. Schönauer, R. Weiss (Eds.), Special Issue on Iterative Methods for Linear Systems Applied Numerical Methods, 1995, pp. 33-56.; R. Weiss, A theoretical overview of Krylov subspace methods, in: W. Schönauer, R. Weiss (Eds.), Special Issue on Iterative Methods for Linear Systems Applied Numerical Methods, 1995, pp. 33-56. · Zbl 0854.65031 |
| [33] | Freund, R. W.; Nachtigal, N. M., QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60, 315-339 (1991) · Zbl 0754.65034 |
| [34] | Gutknecht, Martin H.; Rozloz˘ník, Miroslav, Residual smoothing techniques: do they improve the limiting accuracy of iterative solvers?, BIT, 41, 086-114 (2001) · Zbl 0984.65026 |
| [35] | Gutknecht, Martin H.; Rozloz˘ník, Miroslav, By how much can residual minization accelerate the convergence of orthogonal residual methods?, Numer. Algo., 27, 189-213 (2001) · Zbl 0987.65032 |
| [36] | Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025 |
| [37] | Freund, R. W., A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Comput., 14, 470-482 (1993) · Zbl 0781.65022 |
| [38] | Brown, P. N., A therical comparison of the Arnoldi and GMRES algorithms, SIAM J. Sci. Statist. Comput., 12, 58-78 (1991) · Zbl 0719.65022 |
| [39] | Walker, H. F., Residual smoothing and peak/plateau behavior in Krylov subspace methods, Appl. Numer. Math., 19, 279-286 (1995) · Zbl 0855.65023 |
| [40] | Cullum, J., Peaks, plateaus, numerical instabilities in a Galerkin/minimal residual pair of methods for solving \(Ax = b\), Appl. Numer. Math., 19, 255-278 (1995) · Zbl 0855.65022 |
| [41] | Cullum, J.; Greenbaum, A., Relations between Galerkin and norm-minimizing iterative methods for solving linear systems, SIAM J. Matrix Anal. Appl., 17, 223-247 (1996) · Zbl 0855.65021 |
| [42] | H. Sadok, Analysis of the convergence of the minimal and the orthogonal residual methods, Reprint, 1997.; H. Sadok, Analysis of the convergence of the minimal and the orthogonal residual methods, Reprint, 1997. |
| [43] | Eiermann, M.; Ernst, O., Geometric aspects in the theory of Krylov space methods, Acta Numer., 10, 251-312 (2001) · Zbl 1105.65328 |
| [44] | Stiefel, E., Relaxationsmethoden bester Strategie zur Lösung linearer Gleichungssysteme, Comment. Math. Helv., 29, 157-179 (1955) · Zbl 0066.36703 |
| [45] | van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems (2003), Cambridge University Press: Cambridge University Press Cambridge, pp. 97-98 · Zbl 1023.65027 |
| [46] | Sogabe, T.; Sugihara, M.; Zhang, S.-L., An extension of the conjugate residual method to nonsymmetric linear systems, J. Comput. Appl. Math., 226, 103-113 (2009) · Zbl 1170.65026 |
| [47] | T. Sogabe, Extensions of the conjugate residual method, Ph.D. Dissertation, University of Tokyo, 2006.; T. Sogabe, Extensions of the conjugate residual method, Ph.D. Dissertation, University of Tokyo, 2006. |
| [48] | 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. Sci. Stat. Comput., 13, 631-644 (1992) · Zbl 0761.65023 |
| [49] | Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bureau Standards, 45, 255-281 (1950) |
| [50] | Parlett, B.; Taylor, D.; Liu, Z.-S., A look-ahead Lanczos algorithm for unsymmetric matrices, Math. Comput., 44, 105-124 (1985) · Zbl 0564.65022 |
| [51] | Parlett, B., Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl., 13, 567-593 (1992) · Zbl 0754.65040 |
| [52] | Freund, R.; Gutknecht, M. H.; Nachtigal, N., An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. Stat. Comput., 14, 137-158 (1993) · Zbl 0770.65022 |
| [53] | Gutknecht, M. H., Lanczos-type solvers for nonsymmetric linear systems of equations, Acta Numer., 6, 271-397 (1997) · Zbl 0888.65030 |
| [54] | Day, D., An efficient implementation of the nonsymmetric Lanczos algorithms, SIAM J. Matrix Anal. Appl., 18, 566-589 (1997) · Zbl 0873.65037 |
| [55] | Barrett, R.; Berry, M. W.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H. A., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), SIAM: SIAM Philadelphia, PA |
| [56] | Sleijpen, G. L.G.; van der Vorst, H. A., An overview of approaches for the stable computation of hybrid BiCG method, Appl. Numer. Math., 19, 235-254 (1995) · Zbl 0856.65022 |
| [57] | Gutknecht, M. H., Variants of BiCGSTAB for matrices with complex spectrum, SIAM J. Sci. Comput., 14, 1020-1033 (1993) · Zbl 0837.65031 |
| [58] | Sleijpen, G. L.G.; Fokkema, D. R., BiCGSTAB(l) for linear equations involving unsymmetric matrices with complex spectrum, Electron. Trans. Numer. Anal., 1, 11-32 (1993) · Zbl 0820.65016 |
| [59] | Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual algorithm for solving a nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [60] | Benzi, M., Preconditioning techniques for large linear systems: a survey, J. Comput. Phys., 182, 418-477 (2002) · Zbl 1015.65018 |
| [61] | Davis, T., The University of Florida Sparse Matrix Collection, NA Digest, 97, 23 (1997) |
| [62] | van der Vorst, H. A., The convergence behavior of preconditioned CG and CG-S in the presence of rounding errors, Lecture Notes Math., 1457, 126-136 (1990) · Zbl 0714.65034 |
| [63] | Saad, Y.; van der Vorst, H. A., Iterative solution of linear systems in the 20th century, J. Comput. Appl. Math., 123, 1-33 (2000) · Zbl 0965.65051 |
| [64] | M.H. Gutknecht, Residual smoothing for Krylov space solvers: does it help at all? in: Seminar for Applied Mathematics, ETH Zurich, <http://www.sam.math.ethz.ch/ mhg>; M.H. Gutknecht, Residual smoothing for Krylov space solvers: does it help at all? in: Seminar for Applied Mathematics, ETH Zurich, <http://www.sam.math.ethz.ch/ mhg> |
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.
