zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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:
65F10Iterative methods for linear systems
WorldCat.org
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
[3] Bai, Z. -Z.: Structured preconditioners for nonsingular matrices of block two-by-two structures, Math. comp. 75, 791-815 (2006) · Zbl 1091.65041 · doi:10.1090/S0025-5718-05-01801-6
[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 · doi:10.1137/S0895479801395458
[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 · doi:10.1137/S1064827503428114
[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 · doi:10.1002/nla.517
[8] Benzi, M.; Tuma, M.: A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. comput. 19, 968-994 (1998) · Zbl 0930.65027 · doi:10.1137/S1064827595294691
[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 · doi:10.1002/(SICI)1099-1506(199611/12)3:6<473::AID-NLA85>3.0.CO;2-J
[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 · doi:10.1137/0915023
[11] 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
[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 · doi:10.1137/0720023
[14] Fletcher, R.: Conjugate gradient methods for indefinite systems, Lecture notes in math. 506, 73-89 (1976) · 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 · doi:10.1137/0914029
[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 · doi:10.1007/BF01385726
[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
[18] Golub, G. H.; Van Loan, C. F.: Matrix computations, (1996) · 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 · doi:10.1137/S1064827594276552
[20] Gutknecht, M. H.: Variants of bicgstab for matrices with complex spectrum, SIAM J. Sci. comput. 14, 1020-1033 (1993) · Zbl 0837.65031 · doi:10.1137/0914062
[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 · doi:10.1002/nme.1620210711
[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 · doi:10.1137/0614004
[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 · doi:10.2307/2005786
[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 · doi:10.1137/0712047
[28] Saad, Y.: Krylov subspace methods for solving large unsymmetric linear systems, Math. comp. 37, 105-126 (1981) · Zbl 0474.65019 · doi:10.2307/2007504
[29] 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 Lu factorization, Numer. linear algebra appl. 4, 387-402 (1994) · Zbl 0838.65026 · doi:10.1002/nla.1680010405
[31] Saad, Y.: Iterative methods for sparse linear systems, (2003) · Zbl 1031.65046
[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 · doi:10.1137/0907058
[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 · emis:journals/ETNA/vol.1.1993/
[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 · doi:10.1016/j.cam.2005.07.032
[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 · doi:10.1137/0910004
[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 · doi:10.1137/0915006
[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 · doi:10.1137/0913035
[38] Van Der Vorst, H. A.: Iterative Krylov methods for large linear systems, (2003) · 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 · doi:10.1137/S1064827592236313