×

A stabilized GMRES method for singular and severely ill-conditioned systems of linear equations. (English) Zbl 1492.65095

Summary: Consider using the right-preconditioned GMRES (AB-GMRES) for obtaining the minimum-norm solution of inconsistent underdetermined systems of linear equations. K. Morikuni [Inner-iteration preconditioning for least squares problems (PhD thesis). Department of Informatics, School of Multidisciplinary Sciences, The Graduate University for Advanced Studies (2013)] showed that for some inconsistent and ill-conditioned problems, the iterates may diverge. This is mainly because the Hessenberg matrix in the GMRES method becomes very ill-conditioned so that the backward substitution of the resulting triangular system becomes numerically unstable. We propose a stabilized GMRES based on solving the normal equations corresponding to the above triangular system using the standard Cholesky decomposition. This has the effect of shifting upwards the tiny singular values of the Hessenberg matrix which lead to an inaccurate solution. We analyze why the method works. Numerical experiments show that the proposed method is robust and efficient, not only for applying AB-GMRES to underdetermined systems, but also for applying GMRES to severely ill-conditioned range-symmetric systems of linear equations.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F25 Orthogonalization in numerical linear algebra

References:

[1] ADVANPIX LLC.: Multiprecision Computing Toolbox for MATLAB. https://www.advanpix.com/. Version 4.4.5.12711
[2] Björck, Å., Numerical Methods for Least Squares Problems (1996), PA: SIAM. Philadelphia, PA · Zbl 0847.65023 · doi:10.1137/1.9781611971484
[3] Brezinski, C.; Rodriguez, G.; Seatzu, S., Error estimates for the regularization of least squares problems, Numer. Algorithms, 51, 1, 61-76 (2009) · Zbl 1166.65331 · doi:10.1007/s11075-008-9243-2
[4] Brown, P.; Walker, H., GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18, 1, 37-51 (1997) · Zbl 0876.65019 · doi:10.1137/S0895479894262339
[5] Calvetti, D.; Lewis, B.; Reichel, L., GMRES-type methods for inconsistent systems, Linear Algebra Appl., 316, 1-3, 157-169 (2000) · Zbl 0963.65042 · doi:10.1016/S0024-3795(00)00064-1
[6] Davis, T.; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38, 1, 1-25 (2011) · Zbl 1365.65123
[7] Fong, DCL; Saunders, M., LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput., 33, 5, 2950-2971 (2011) · Zbl 1232.65052 · doi:10.1137/10079687X
[8] Foster, L.: San Jose State University Singular Matrix Database. http://www.math.sjsu.edu/singular/matrices/
[9] Hansen, P., Discrete Inverse Problems: Insight and Algorithms (2010), PA: SIAM. Philadelphia, PA · Zbl 1197.65054 · doi:10.1137/1.9780898718836
[10] Hayami, K.; Sugihara, M., A geometric view of Krylov subspace methods on singular systems, Numer. Linear Algebra Appl., 18, 3, 449-469 (2011) · Zbl 1245.65037 · doi:10.1002/nla.737
[11] Hayami, K.; Yin, J.; Ito, T., GMRES methods for least squares problems, SIAM J. Matrix Anal. Appl., 31, 5, 2400-2430 (2010) · Zbl 1215.65071 · doi:10.1137/070696313
[12] Hestenes, M.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49, 6, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044
[13] Higham, N.J.: The Test Matrix Toolbox for MATLAB (version 3.0). University of Manchester, Manchester (1995)
[14] Higham, NJ, Accuracy and Stability of Numerical Algorithms (2002), PA: SIAM. Philadelphia, PA · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[15] Horn, RA; Johnson, CR, Matrix Analysis (2012), New York, NY: Cambridge University Press, New York, NY · doi:10.1017/CBO9781139020411
[16] Iri, M.: General Theory of Linear Algebra. Asakura, (in Japanese) (2009)
[17] Meza, JC; Symes, WW, Deflated Krylov subspace methods for nearly singular linear systems, J. Optim. Theory Appl., 72, 3, 441-457 (1992) · Zbl 0804.65031 · doi:10.1007/BF00939836
[18] Morikuni, K.: Inner-iteration Preconditioning for Least Squares Problems. Doctoral Thesis, Department of Informatics, School of Multidisciplinary Sciences, The Graduate University for Advanced Studies (2013) · Zbl 1269.65039
[19] Morikuni, K.; Hayami, K., Convergence of inner-iteration GMRES methods for rank-deficient least squares problems, SIAM J. Matrix Anal. Appl., 36, 1, 225-250 (2015) · Zbl 1315.65041 · doi:10.1137/130946009
[20] Morikuni, K.; Rozložník, M., On GMRES for singular EP and GP systems, SIAM J. Matrix Anal. Appl., 39, 2, 1033-1048 (2018) · Zbl 1391.65070 · doi:10.1137/17M1128216
[21] Neuman, A.; Reichel, L.; Sadok, H., Algorithms for range restricted iterative methods for linear discrete ill-posed problems, Numer. Algorithms, 59, 2, 325-331 (2012) · Zbl 1236.65040 · doi:10.1007/s11075-011-9491-4
[22] Neuman, A.; Reichel, L.; Sadok, H., Implementations of range restricted iterative methods for linear discrete ill-posed problems, Linear Algebra Appl., 436, 10, 3974-3990 (2012) · Zbl 1241.65045 · doi:10.1016/j.laa.2010.08.033
[23] Paige, C.; Rozložník, M.; Strakoš, Z., Modified Gram-Schmidt (mgs), least squares, and backward stability of MGS-GMRES, SIAM J. Matrix Anal. Appl., 28, 1, 264-284 (2006) · Zbl 1113.65028 · doi:10.1137/050630416
[24] Paige, CC; Saunders, MA, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 4, 617-629 (1975) · Zbl 0319.65025 · doi:10.1137/0712047
[25] Paige, CC; Saunders, MA, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 1, 43-71 (1982) · Zbl 0478.65016 · doi:10.1145/355984.355989
[26] Reichel, L.; Ye, Q., Breakdown-free GMRES for singular systems, SIAM J. Matrix Anal. Appl., 26, 4, 1001-1021 (2005) · Zbl 1086.65030 · doi:10.1137/S0895479803437803
[27] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), PA: SIAM. Philadelphia, PA · Zbl 1002.65042 · doi:10.1137/1.9780898718003
[28] Saad, Y.; Schultz, MH, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[29] Sugihara, K., Hayami, K., Liao, Z.: GMRES using pseudo-inverse for range symmetric singular systems. (in revision) · Zbl 1524.65150
[30] Tebbens, JD; Tůma, M., On incremental condition estimators in the 2-norm, SIAM J. Anal. Appl., 35, 1, 174-197 (2014) · Zbl 1299.65089 · doi:10.1137/130922872
[31] Yamamoto, Y.; Nakatsukasa, Y.; Yanagisawa, Y.; Fukaya, T., Roundoff error analysis of the CholeskyQR2 algorithm, Electron. Trans. Numer. Anal., 44, 1, 306-326 (2015) · Zbl 1330.65049
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.