×

Inexact GMRES for singular linear systems. (English) Zbl 1161.65024

The author considers the iterative solution of large sparse \(n\times n\) linear systems of the form \(Ax=b\) with a Krylow subspace method. He shows theoretically and experimentally that an inexact generalized minimal residual (GMRES) method can be applied to singular systems, in particular, to those obtained from Markov chain modeling. Inexact and exact GMRES are compared for consistent singular systems obtained from Markov chain matrices. It is seen that one can save the computational effort using inexact matrix-vector products. These savings come with no deterioration of the overall convergence. In cases where the index \(k_0\) of the matrix is larger than one, the right-hand side needs to lie on (or be close to) the range of \(A^{k_0}\) for the methods to work well.

MSC:

65F10 Iterative numerical methods for linear systems
65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains

Software:

MARCA; METIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. A. Barker, Numerical solutions of sparse singular systems of equations arising from ergodic Markov chains, Commun. Stat. Stochastic Models, 5 (1989), pp. 335–381. · Zbl 0678.65028
[2] M. Benzi and B. Uçar, Block triangular preconditioners for M-matrices and Markov chains, Electron. Trans. Numer. Anal., 26 (2007), pp. 209–227. · Zbl 1171.65388
[3] Å. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996. · Zbl 0847.65023
[4] A. Bouras and V. Frayssé, Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 660–678. · Zbl 1075.65041
[5] P. Brown and H. Walker, GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 37–51. · Zbl 0876.65019
[6] D. Calvetti, B. W. Lewis, and L. Reichel, GMRES-type methods for inconsistent systems, Linear Algebra Appl., 316 (2000), pp. 157–169. · Zbl 0963.65042
[7] Z. H. Cao and M. Wang, A note on Krylov subspace methods for singular systems, Linear Algebra Appl., 350 (2002), pp. 285–288. · Zbl 1007.15007
[8] J. Van den Eshof and G. Sleijpen, Inexact Krylov subspace methods for linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 125–153. · Zbl 1079.65036
[9] R. W. Freund and M. Hochbruck, On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling, Numer. Linear Algebra Appl., 1 (1994), pp. 403–420. · Zbl 0840.65021
[10] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, NY, 1999.
[11] G. Karypis and V. Kumar, Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices version 4.0, 1998.
[12] C. C. Paige and Z. Strakǒs, Scaled total least squares fundamentals, Numer. Math., 91 (2002), pp. 117–146. · Zbl 0998.65046
[13] B. Philippe, Y. Saad, and W. J. Stewart, Numerical methods in Markov chain modeling, Oper. Res., 40 (1992), pp. 1156–1179. · Zbl 0764.65095
[14] L. Reichel and Q. Ye, Breakdown-free GMRES for singular systems, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 1001–1021. · Zbl 1086.65030
[15] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edn., The PWS Publishing Company, Boston, USA 1996, SIAM, Philadelphia, PA, 2003. · Zbl 1031.65046
[16] Y. Saad and M. H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, J. Sci. Stat. Comput., 7 (1986), pp. 856–869. · Zbl 0599.65018
[17] V. Simoncini and D. B. Szyld, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput., 25 (2003), pp. 454–477. · Zbl 1048.65032
[18] V. Simoncini and D. B. Szyld, Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14 (2007), pp. 1–59. · Zbl 1199.65112
[19] L. Smoch, Some results about GMRES in the singular case, Numer. Algorithms, 22 (1999), pp. 193–212. · Zbl 0945.65027
[20] W. J. Stewart, Introduction to the Numerical Solution of Markov Chains, Princeton University Press, Princeton, NJ, 1994. · Zbl 0821.65099
[21] W. J. Stewart, Marca models: A collection of Markov chain models, Available at http://www4.ncsu.edu/illy/MARCA_Models/MARCA_Models.html (accessed August 2006).
[22] Y. Wei and H. Wu, Convergence properties of Krylov subspace methods for singular linear systems with arbitrary index, J. Comput. Appl. Math., 114 (2000), pp. 305–318. · Zbl 0959.65046
[23] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, UK, 1965. · Zbl 0258.65037
[24] N. Zhang and Y. Wei, A note on solving EP inconsistent linear systems, Appl. Math. Comput., 169 (2005), pp. 8–15. · Zbl 1087.65544
[25] N. Zhang and Y. Wei, Solving EP singular linear systems, Int. J. Comput. Math., 81 (2005), pp. 1395–1405. · Zbl 1069.65046
[26] J. Zhou and Y. Wei, DFOM algorithm and error analysis for projection methods for solving singular linear system, Appl. Math. Comput., 157 (2004), pp. 313–329. · Zbl 1056.65030
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.