×

An extension of the conjugate residual method to nonsymmetric linear systems. (English) Zbl 1170.65026

This paper adapts the conjugate residual method (CR) that solves large sparse symmetric systems to general sparse matrix systems. Special attention is paid to keep the computational effort constantly low per iteration, such as done with a two-sided Lanczos process in the bi-conjugate gradient method (Bi-CG) with short term recurrences. The paper describes and analyses the bi-conjugate gradient method in this light and extends conjugate residual to the new bi-conjugate residual algorithm (Bi-CR) for non-symmetric systems. The properties and convergence behavior of Bi-CR is studied and compared to Bi-CG. In experiments, Bi-CR appears to offer smoother and often faster convergence than Bi-CG.

MSC:

65F10 Iterative numerical methods for linear systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnoldi, W. E., The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9, 17-29 (1951) · Zbl 0042.12801
[2] Z. Bai, D. Day, J. Demmel, J. Dongarra, A test matrix collection for non-Hermitian eigenvalue problems, Tech. Rep. CS-97-355, Department of Computer Science, University of Tennessee, Knoxville, TN, March, 1997; Z. Bai, D. Day, J. Demmel, J. Dongarra, A test matrix collection for non-Hermitian eigenvalue problems, Tech. Rep. CS-97-355, Department of Computer Science, University of Tennessee, Knoxville, TN, March, 1997
[3] Bai, Z.-Z., Structured preconditioners for nonsingular matrices of block two-by-two structures, Math. Comp., 75, 791-815 (2006) · Zbl 1091.65041
[4] Bai, Z.-Z., Splitting iteration methods for non-Hermitian positive definite systems of linear equations, Hokkaido Math. J., 36, 801-814 (2007) · Zbl 1138.65027
[5] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032
[6] Bai, Z.-Z.; Golub, G. H.; Lu, L.-Z.; Yin, J.-F., Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., 26, 844-863 (2005) · Zbl 1079.65028
[7] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., On successive overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 14, 319-335 (2007) · Zbl 1199.65097
[8] Benzi, M.; Tůma, M., A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19, 968-994 (1998) · Zbl 0930.65027
[9] Broyden, C. G.; Boschetti, M. A., A comparison of three basic conjugate direction methods, Numer. Linear Algebra Appl., 3, 473-489 (1996) · Zbl 0906.65030
[10] Chan, T. F.; Gallopoulos, E.; Simoncini, V.; Szeto, T.; Tong, C. H., A quasi-minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems, SIAM J. Sci. Comput., 15, 338-347 (1994) · Zbl 0803.65038
[11] T. Davis, UF Sparse matrix collection. http://www.cise.ufl.edu/research/sparse/matrices; T. Davis, UF Sparse matrix collection. http://www.cise.ufl.edu/research/sparse/matrices
[12] I.S. Duff, R.G. Grimes, J.G. Lewis, User’s guide for the Harwell-Boeing sparse matrix collection, Tech. Rep. RAL-92-086, Rutherford Appleton Laboratory, Chilton, UK, 1992; I.S. Duff, R.G. Grimes, J.G. Lewis, User’s guide for the Harwell-Boeing sparse matrix collection, Tech. Rep. RAL-92-086, Rutherford Appleton Laboratory, Chilton, UK, 1992
[13] Eisenstat, S. C.; Elman, H. C.; Schultz, M. H., Variational iterative methods for nonsymmeric systems of linear equations, SIAM J. Sci. Numer Anal., 20, 345-537 (1983) · Zbl 0524.65019
[14] Fletcher, R., Conjugate gradient methods for indefinite systems, (Lecture Notes in Math., vol. 506 (1976), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York), 73-89 · Zbl 0326.65033
[15] 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
[16] 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
[17] R.W. Freund, T. Szeto, A quasi-minimal residual squared algorithm for non-Hermitian linear systems, in: Proceedings of the Second Copper Mountain Conference on Iterative Methods 1992; R.W. Freund, T. Szeto, A quasi-minimal residual squared algorithm for non-Hermitian linear systems, in: Proceedings of the Second Copper Mountain Conference on Iterative Methods 1992
[18] Golub, G. H.; van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore and London · Zbl 0865.65009
[19] Grote, M.; Huckle, T., Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18, 838-853 (1997) · Zbl 0872.65031
[20] Gutknecht, M. H., Variants of BiCGSTAB for matrices with complex spectrum, SIAM J. Sci. Comput., 14, 1020-1033 (1993) · Zbl 0837.65031
[21] Gutknecht, M. H., Lanczos-type solvers for nonsymmetric linear systems of equations, Acta Numer., 6, 271-397 (1997) · Zbl 0888.65030
[22] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards, 49, 409-436 (1952) · Zbl 0048.09901
[23] Jackson, C. P.; Robinson, P. C., A numerical study of various algorithms related to the preconditioned conjugate gradient method, Internat. J. Numer. Methods Engrg., 21, 1315-1338 (1985) · Zbl 0576.65021
[24] Kolotilina, L. Yu.; Yeremin, A. Yu., Factorized sparse approximate inverse preconditionings I: Theory, SIAM J. Matrix Anal. Appl., 14, 45-58 (1993) · Zbl 0767.65037
[25] Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards, 49, 33-53 (1952)
[26] 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. Comp., 31, 148-162 (1977) · Zbl 0349.65020
[27] 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
[28] Saad, Y., Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp., 37, 105-126 (1981) · Zbl 0474.65019
[29] Y. Saad, SPARSKIT: A basic tool kit for sparse matrix computation, Tech. Rep. CSRD TR 1029, CSRD, University of Illinois, Urbana, IL, 1990; Y. Saad, SPARSKIT: A basic tool kit for sparse matrix computation, Tech. Rep. CSRD TR 1029, CSRD, University of Illinois, Urbana, IL, 1990
[30] Saad, Y., ILUT: a dual threshold incomplete \(L U\) factorization, Numer. Linear Algebra Appl., 4, 387-402 (1994) · Zbl 0838.65026
[31] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia, PA · Zbl 1002.65042
[32] Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[33] Sleijpen, G. L.G.; Fokkema, D. R., BICGSTAB \(( \ell )\) for linear equations involving unsymmetric matrices with complex spectrum, Electron. Trans. Numer. Anal., 1, 11-32 (1993) · Zbl 0820.65016
[34] 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
[35] Sonneveld, P., CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10, 36-52 (1989) · Zbl 0666.65029
[36] Tong, C. H., A family of quasi-minimal residual methods for nonsymmetric linear systems, SIAM J. Sci. Comput., 15, 89-105 (1994) · Zbl 0799.65035
[37] 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
[38] van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1023.65027
[39] Zhang, S.-L., GPBi-CG: Generalized product-type methods based on Bi-CG for solving nonsymmetric linear systems, SIAM J. Sci. Comput., 18, 537-551 (1997) · Zbl 0872.65023
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.