On the convergence of Q-OR and Q-MR Krylov methods for solving nonsymmetric linear systems. (English) Zbl 1350.65023

This theoretical paper studies convergence of general classes of quasi-minimal residual (Q-MR) and quasi-orthogonal residual (Q-MO) methods for solving nonsymmetric systems of linear algebraic equations. Relating these classes to the generalized minimal residual (GMRES) method and the full orthogonalization method (FOM), respectively, relation of eigenvalues and eigenvectors to convergence behavior is discussed. The existence of a linear system with any prescribed spectrum and the convergence curve are analyzed in details. The paper is well written bringing some new insight into the behavior of nonoptimal Krylov subspace methods.


65F10 Iterative numerical methods for linear systems
Full Text: DOI


[1] Arioli, M; Pták, V; Strakoš, Z, Krylov sequences of maximal length and convergence of GMRES, BIT, 38, 636-643, (1998) · Zbl 0916.65031
[2] Arnoldi, WE, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Q. Appl. Math., 9, 17-29, (1951) · Zbl 0042.12801
[3] Brown, PN, A theoretical comparison of the Arnoldi and GMRES algorithms, SIAM J. Sci. Stat. Comput., 12, 58-78, (1991) · Zbl 0719.65022
[4] Brown, PN; Hindmarsh, AC, Reduced storage matrix methods in stiff ODE systems, Appl. Math. Comput., 31, 40-91, (1989) · Zbl 0677.65074
[5] Choi, S-CT; Paige, CC; Saunders, MA, MINRES-QLP: a Krylov subspace method for indefinite or singular symmetric systems, SIAM J. Sci. Comput., 33, 1810-1836, (2011) · Zbl 1230.65050
[6] Cullum, J, Iterative methods for solving \(Ax=b\), GMRES/FOM versus QMR/bicg, Adv. Comput. Math., 6, 1-24, (1996) · Zbl 0873.65028
[7] Cullum, J; Greenbaum, A, Relations between Galerkin and norm-minimizing iterative methods for solving linear systems, SIAM J. Matrix Anal. Appl., 17, 223-247, (1996) · Zbl 0855.65021
[8] Duintjer Tebbens, J; Meurant, G, Any Ritz value behavior is possible for Arnoldi and for GMRES, SIAM J. Matrix Anal. Appl., 33, 958-978, (2012) · Zbl 1266.65060
[9] Duintjer Tebbens, J; Meurant, G, Prescribing the behavior of early terminating GMRES and Arnoldi iterations, NumER. Algorithm, 65, 69-90, (2014) · Zbl 1288.65037
[10] Duintjer Tebbens, J., Meurant, G.: On the admissible convergence curves for restarted GMRES. submitted (2015) · Zbl 1312.65050
[11] Duintjer Tebbens, J; Meurant, G; Sadok, H; Strakoš, Z, On investigating GMRES convergence using unitary matrices, Lin. Alg. Appl., 450, 83-107, (2014) · Zbl 1302.65076
[12] Eiermann, M; Ernst, OG, Geometric aspects of the theory of Krylov subspace methods, Acta Numer., 10, 251-312, (2001) · Zbl 1105.65328
[13] Fletcher, R.: Conjugate gradient methods for indefinite systems. In: Numerical analysis of Proceedings of 6th Biennial Dundee Conference, University of Dundee, Dundee, 1975, Lecture Notes in Mathematics, vol. 506, pp. 73-89. Springer, Berlin (1976)
[14] Freund, RW; Nachtigal, NM, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60, 315-339, (1991) · Zbl 0754.65034
[15] Freund, RW; Nachtigal, NM, An implementation of the QMR method based on coupled two-term recurrences, SIAM J. Sci. Comput., 15, 313-337, (1994) · Zbl 0803.65036
[16] Freund, RW; Nachtigal, NM, Software for simplified Lanczos and QMR algorithms, Appl. Numer. Math., 19, 319-341, (1995) · Zbl 0853.65041
[17] Greenbaum, A.: Iterative Methods for Solving Linear Systems, vol. 17 of Frontiers in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1997) · Zbl 0883.65022
[18] Greenbaum, A; Pták, V; Strakoš, Z, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17, 465-469, (1996) · Zbl 0857.65029
[19] Greenbaum, A., Strakoš, Z.: Matrices that generate the same Krylov residual spaces. In: Golub, G.H., Luskin, M., Greenbaum, A. (eds.) Recent Advances in Iterative Methods, vol. 60 of IMA Vol. Mathematics Application, pp. 95-118. Springer, New York (1994) · Zbl 0803.65029
[20] Heyouni, M; Sadok, H, On a variable smoothing procedure for Krylov subspace methods, Linear Algebra Appl., 268, 131-149, (1998) · Zbl 0886.65031
[21] Jea, KC; Young, DM, On the simplification of generalized conjugate-gradient methods for nonsymmetrizable linear systems, Linear Algebra Appl., 52, 399-417, (1983) · Zbl 0535.65018
[22] Jia, Z, On IGMRES: an incomplete generalized minimal residual method for large unsymmetric linear systems, Sci. China Ser. A, 41, 1278-1288, (1998) · Zbl 0920.65017
[23] Joubert, W, Lanczos methods for the solution of nonsymmetric systems of linear equations, SIAM J. Matrix Anal. Appl., 13, 926-943, (1992) · Zbl 0758.65026
[24] Lanczos, C, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Stand., 49, 33-53, (1952)
[25] Liesen, J., Strakoš, Z.: Krylov Subspace Methods, Principles and Analysis. Oxford University Press, Oxford (2012) · Zbl 1307.65001
[26] Meurant, G, GMRES and the arioli, pták, and strakoš parametrization, BIT, 52, 687-702, (2012) · Zbl 1253.65047
[27] Meurant, G; Tebbens, JD, The role eigenvalues play in forming GMRES residual norms with non-normal matrices, Numer. Algorithms, 68, 143-165, (2015) · Zbl 1312.65050
[28] Saad, Y, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comput., 37, 105-126, (1981) · Zbl 0474.65019
[29] Saad, Y, The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems, SIAM J. Numer. Anal., 19, 485-506, (1982) · Zbl 0483.65022
[30] Saad, Y; Schultz, MH, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869, (1986) · Zbl 0599.65018
[31] Sadok, H, CMRH: a new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm, Numer. Algorithms, 20, 303-321, (1999) · Zbl 0936.65031
[32] Sadok, H; Szyld, DB, A new look at CMRH and its relation to GMRES, BIT, 52, 485-501, (2012) · Zbl 1247.65045
[33] Schweitzer, M.: Any cycle-convergence curve is possible for restarted FOM. Preprint BUW-IMACM 14/19, Bergische Universität Wuppertal (2014) · Zbl 0761.65023
[34] Simoncini, V, On the convergence of restarted Krylov subspace methods, SIAM J. Matrix Anal. Appl., 22, 430-452, (2000) · Zbl 0969.65023
[35] Simoncini, V; Szyld, DB, The effect of non-optimal bases on the convergence of Krylov subspace methods, Numer. Math., 100, 711-733, (2005) · Zbl 1118.65022
[36] Sonneveld, P, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10, 36-52, (1989) · Zbl 0666.65029
[37] Tichý, P.: O některých otevřených problémech v krylovovských metodách. PhD thesis (in Czech). Charles University, Prague (2002) · Zbl 0599.65018
[38] Vorst, HA, 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
[39] van der Vorst, H.A.: Iterative Krylov Methods for Large Linear Systems, vol. 13 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2003) · Zbl 1178.65034
[40] Vecharynski, E; Langou, J, Any admissible cycle-convergence behavior is possible for restarted GMRES at its initial cycles, Numer. Lin. Algebra Appl., 18, 499-511, (2011) · Zbl 1249.65073
[41] Vinsome, P.K.W.: Orthomin, an iterative method for solving sparse sets of simultaneous linear equations. In Proceedings of the Fourth Symposium on Reservoir Simulation, pp. 149-159. SPE (1976) · Zbl 1118.65022
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.