×

A geometric view of Krylov subspace methods on singular systems. (English) Zbl 1245.65037

Numer. Linear Algebra Appl. 18, No. 3, 449-469 (2011); corrigendum ibid 21, No. 5, 701-702 (2014); corrigendum 2 ibid. 28, No. 4, e2368, 7 p. (2021).
Three Krylov subspace methods, GMRES, restarted GMRES and restarted GCR, are analyzed in their behavior when applied to singular square nonsymmetric systems of linear equations. With an emphasis on geometric aspects, the quantities in the algorithms are decomposed into their components in the range of the coefficient matrix and its orthogonal complement. Extensions, new interpretations and new proofs of previous results of Brown and Walker on when these algorithms yield least-squares solutions and when they break down, i.e., terminate before such a solution is found, are given. The paper concludes with examples of singular systems arising in the discretization of two-point boundary value problems.

MSC:

65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
34B05 Linear boundary value problems for ordinary differential equations
65L10 Numerical solution of boundary value problems involving ordinary differential equations

Software:

DGMRES; MARCA; CGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fletcher, Lecture Notes in Mathematics, in: Numerical Analysis Dundee 1975 pp 73– (1976)
[2] Sonneveld, CGS: a fast Lanczos-type solver for nonsymmetric linear systems, SIAM Journal on Statistical and Scientific Computing 10 pp 36– (1989) · Zbl 0666.65029
[3] van der Vorst, Bi-CGSTAB: a more smoothly converging variant of CG-S for the solution of nonsymmetric linear systems, SIAM Journal on Statistical and Scientific Computing 13 pp 631– (1992) · Zbl 0761.65023
[4] Freund, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numerische Mathematik 60 pp 315– (1991) · Zbl 0754.65034
[5] Freund, A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM Journal on Scientific Computing 14 pp 425– (1993) · Zbl 0781.65022
[6] Saad, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Statistical and Scientific Computing 7 pp 856– (1986) · Zbl 0599.65018
[7] Eisenstat, Variational iterative methods for nonsymmetric systems of linear equations, SIAM Journal on Numerical Analysis 20 pp 345– (1983) · Zbl 0524.65019
[8] Biro, On the use of the magnetic vector potential in the nodal and edge finite element analysis of 3-D magnetostatic problems, IEEE Transactions on Magnetics 32 pp 651– (1996)
[9] Ren, Influence of the R.H.S. on the convergence behaviour of the curl-curl equation, IEEE Transactions on Magnetics 32 pp 655– (1996)
[10] Igarashi, Inverse Problems in Engineering Mechanics II pp 467– (2000)
[11] Strouboulis, The design and analysis of the generalized finite element method, Computer Methods in Applied Mechanics and Engineering 181 pp 43– (2000) · Zbl 0983.65127
[12] Tanabe, The conjugate gradient method for computing all the extremal stationary probability vectors of a stochastic matrix, Annals of the Institute of Statistical Mathematics pp 173– (1985) · Zbl 0569.60069
[13] Freund, On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling, Numerical Linear Algebra with Applications 1 pp 403– (1994) · Zbl 0840.65021
[14] Dayar, Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM Journal on Scientific Computing 21 pp 1691– (2000) · Zbl 0957.60076
[15] Tanabe, Characterization of linear stationary processes for solving singular system of linear equations, Numerische Mathematik 22 pp 349– (1974) · Zbl 0312.65031
[16] Dax, The convergence of linear stationary iterative processes for solving singular unstructured systems of linear equations, SIAM Review 32 pp 611– (1990) · Zbl 0718.65021
[17] Eiermann, On the solution of singular linear systems of algebraic equations by semiiterative methods, Numerische Mathematik 53 pp 265– (1988) · Zbl 0655.65049
[18] Hanke, A Chebyshev-like semiiteration for inconsistent linear systems, Electronic Transactions on Numerical Analysis 1 pp 89– (1993) · Zbl 0809.65039
[19] Sidi, Orthogonal polynomials and semi-iterative methods for the Drazin-inverse solution of singular linear systems, Numerische Mathematik 93 pp 563– (2003) · Zbl 1019.65026
[20] Kammerer, On the convergence of the conjugate gradient method for singular linear operator equations, SIAM Journal on Numerical Analysis 9 pp 165– (1972) · Zbl 0243.65026
[21] Kaasschieter, Preconditioned conjugate gradients for solving singular systems, Journal of Computational and Applied Mathematics 24 pp 265– (1988) · Zbl 0659.65031
[22] Fischer, A note on conjugate-gradient type methods for indefinite and/or inconsistent linear systems, Numerical Algorithms 11 pp 181– (1996) · Zbl 0847.65018
[23] Wei, Convergence properties of Krylov subspace methods for singular linear systems with arbitrary index, Journal of Computational and Applied Mathematics 114 pp 305– (2000) · Zbl 0959.65046
[24] Abe, Convergence theory of the CR method for linear singular systems, Transactions of the Japan Society for Industrial and Applied Mathematics 9 pp 1– (1999)
[25] Hayami, Proceedings of Fifth China-Japan Seminar on Numerical Mathematics pp 117– (2002)
[26] Hayami, On the convergence of the conjugate residual method for singular systems, Transactions of the Japan Society for Industrial and Applied Mathematics 13 pp 1– (2003)
[27] Zhang, Necessary and sufficient conditions for the convergence of Orthomin(k) on inconsistent linear systems, Numerische Mathematik 87 pp 391– (2000) · Zbl 0966.65033
[28] Sidi, A unified approach to Krylov subspace methods for the Drazin-inverse solution of singular nonsymmetric linear systems, Linear Algebra and its Applications 298 pp 99– (1999) · Zbl 0983.65054
[29] Sidi, DGMRES: a GMRES-type algorithm for Drazin-inverse solution of singular nonsymmetric linear systems, Linear Algebra and its Applications 335 pp 189– (2001) · Zbl 0982.65043
[30] Brown, GMRES on (nearly) singular systems, SIAM Journal on Matrix Analysis and Applications 18 pp 37– (1997) · Zbl 0876.65019
[31] Smoch, Some results about GMRES in the singular case, Numerical Algorithms 22 pp 193– (1999) · Zbl 0945.65027
[32] Ipsen, The idea behind Krylov methods, American Mathematical Monthly 105 pp 889– (1998) · Zbl 0982.65034
[33] Calvetti, GMRES-type methods for inconsistent systems, Linear Algebra and its Applications 316 pp 157– (2000) · Zbl 0963.65042
[34] Schneider O Krylov subspace methods and their generalizations for solving singular operator equations with applications to continuous time Markov chains 2005
[35] Washio, Matrix Analysis and Parallel Computing, Proceedings of PCG’94 pp 75– (1994)
[36] Saad, Iterative Methods for Sparse Linear Systems (2003) · Zbl 1031.65046
[37] Elman HC Iterative methods for large, sparse, nonsymmetric systems of linear equations 1982
[38] Mori, Linear Computation (1994)
[39] van der Vorst, GMRESR: a family of nested GMRES methods, Numerical Linear Algebra with Applications 1 pp 369– (1994) · Zbl 0839.65040
[40] de Sturler, Nested Krylov methods based on GCR, Journal of Computational and Applied Mathematics 67 pp 15– (1996) · Zbl 0854.65026
[41] de Sturler, Truncation strategies for optimal Krylov subspace methods, SIAM Journal on Numerical Analysis 36 pp 864– (1999) · Zbl 0960.65031
[42] Langou J GCR vs flexible GMRES 118
[43] Hayami K Sugihara M 2004 http://research.nii.ac.jp/TechReports/04-009E.html
[44] Hayami K Sugihara M 2009 http://research.nii.ac.jp/TechReports/09-007E.html
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.