×

A GMRES convergence analysis for localized invariant subspace ill-conditioning. (English) Zbl 1420.65059

Summary: The Generalized Minimal RESidual (gmres) method is a well-established strategy for iteratively solving a large linear system \(A x = b\), where \(A\in\mathbb{R}^{n\times n}\) is a nonsymmetric and nonsingular coefficient matrix, and \(b\in\mathbb{R}^n\). In the analysis of its convergence for \(A\) diagonalizable, a much used upper bound for the relative residual norm involves a min-max polynomial problem over the set of eigenvalues of \(A\), magnified by the condition number of the eigenvector matrix of \(A\). This latter factor may cause a huge overestimation of the residual norm, making the bound nondescriptive in practice. We show that when a large condition number is caused by the almost linear dependence of a few of the eigenvectors, a more descriptive analysis of the method’s behavior can be performed, irrespective of the location of the corresponding eigenvalues. The new analysis aims at capturing how the gmres polynomial deals with the ill-conditioning; as a by-product, a new upper bound for the gmres residual norm is obtained. A variety of numerical experiments illustrate our findings.

MSC:

65F30 Other matrix algorithms (MSC2010)

Software:

Matlab; MatrixMarket
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Arioli, V. Pták, and Z. Strakoš, Krylov sequences of maximal length and convergence of GMRES, BIT, 38 (1998), pp. 636-643. · Zbl 0916.65031
[2] C. A. Beattie, M. Embree, and D. C. Sorensen, Convergence of polynomial restart Krylov methods for eigenvalue computations, SIAM Rev., 47 (2005), pp. 492-515, ŭlhttps://doi.org/10.1137/S0036144503433077. · Zbl 1073.65028
[3] B. Beckermann, Image numérique, GMRES et polynômes de Faber, C. R. Math. Acad. Sci. Paris Ser. I, 340 (2005), pp. 855-860. · Zbl 1076.47004
[4] S. L. Campbell, I. C. F. Ipsen, C. T. Kelley, and C. D. Meyer, GMRES and the minimal polynomial, BIT, 36 (1996), pp. 664-675. · Zbl 0865.65017
[5] F. Chatelin, Valeurs Propres de Matrices, Masson, Paris, 1988. · Zbl 0691.65018
[6] L. Eldén and V. Simoncini, Solving ill-posed linear systems with GMRES and a singular preconditioner, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1369-1394, https://doi.org/10.1137/110832793. · Zbl 1263.65033
[7] M. Embree, How Descriptive are GMRES Convergence Bounds?, Tech. report 08, Oxford University Computer Laboratory, 1999.
[8] R. W. Freund, Quasi-kernel polynomials and convergence results for quasi-minimal residual iterations, in Numerical Methods in Approximation Theory, Vol. 9, D. Braess and L. L. Schumaker, eds., Birkhäuser, Basel, 1992, pp. 77-95. · Zbl 0814.65035
[9] S. Goossens and D. Roose, Ritz and harmonic Ritz values and the convergence of FOM and GMRES, Numer. Linear Algebra Appl., 6 (1999), pp. 281-293. · Zbl 0983.65034
[10] A. Greenbaum, V. Pták, and Z. Strakoš, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 465-469, https://doi.org/10.1137/S0895479894275030. · Zbl 0857.65029
[11] A. Greenbaum and Z. Strakoš, Matrices that generate the same Krylov residual spaces, in Recent Advances in Iterative Methods, G. Golub, A. Greenbaum, and M. Luskin, eds., Springer-Verlag, New York, 1994, pp. 22-33. · Zbl 0803.65029
[12] A. Greenbaum and L. N. Trefethen, GMRES/CR and Arnoldi/Lanczos as matrix approximation problems, SIAM J. Sci. Comput., 15 (1994), pp. 359-368, https://doi.org/10.1137/0915025. · Zbl 0806.65031
[13] J. Liesen, Computable convergence bounds for GMRES, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 882-903, https://doi.org/10.1137/S0895479898341669. · Zbl 0958.65036
[14] J. Liesen and Z. Strakoš, Convergence of GMRES for tridiagonal Toeplitz matrices, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 233-251, ŭlhttps://doi.org/10.1137/S0895479803424967. · Zbl 1079.65031
[15] J. Liesen and Z. Strakoš, GMRES convergence analysis for a convection-diffusion model problem, SIAM J. Sci. Comput., 26 (2005), pp. 1989-2009, https://doi.org/10.1137/S1064827503430746. · Zbl 1121.65314
[16] J. Liesen and Z. Strakoš, Krylov Subspace Methods. Principles and Analysis, Oxford University Press, 2013. · Zbl 1263.65034
[17] J. Liesen and P. Tichy, Convergence analysis of Krylov subspace methods, GAMM Mitt., 27 (2004), pp. 153-173. · Zbl 1071.65041
[18] The MathWorks, Inc., MATLAB 7, 2017.
[19] Matrix Market, A Visual Repository of Test Data for Use in Comparative Studies of Algorithms for Numerical Linear Algebra, Mathematical and Computational Sciences Division, National Institute of Standards and Technology, http://math.nist.gov/MatrixMarket, 2007.
[20] N. M. Nachtigal, S. C. Reddy, and L. N. Trefethen, How fast are nonsymmetric matrix iterations?, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 778-795, https://doi.org/10.1137/0613049. · Zbl 0754.65036
[21] J. Nocedal and S. Wright, Numerical Optimization, Springer, New York, 1999. · Zbl 0930.65067
[22] C. Paige, B. Parlett, and H. van der Vorst, Approximate solutions and eigenvalue bounds from Krylov subspaces, Numer. Linear Algebra Appl., 2 (1995), pp. 115-134. · Zbl 0831.65036
[23] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869, https://doi.org/10.1137/0907058. · Zbl 0599.65018
[24] G. Sacchi, A New Convergence Model for the GMRES Method, Master’s thesis, Alma Mater Studiorum, Università di Bologna, 2017, https://amslaurea.unibo.it/13501/1/sacchi_giulia_tesi_mag.pdf.
[25] J. A. Sifuentes, M. Embree, and R. B. Morgan, GMRES convergence for perturbed coefficient matrices, with application to approximate deflation preconditioning, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1066-1088, https://doi.org/10.1137/120884328. · Zbl 1314.65051
[26] V. Simoncini, Non-linear spectral perturbation: A qualitative analysis, BIT, 39 (1999), pp. 350-365. · Zbl 0937.65043
[27] 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
[28] V. Simoncini and D. B. Szyld, New conditions for non-stagnation of minimal residual methods, Numer. Math., 109 (2008), pp. 477-487. · Zbl 1151.65026
[29] L. Trefethen and M. Embree, Spectra and Pseudospectra. The Behavior of Non-Normal Matrices and Operators, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
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.