Top

Numerical Algorithms

Published in:

12-12-2019 | Original Paper

On the residual norms, the Ritz values and the harmonic Ritz values that can be generated by restarted GMRES

Authors: Jurjen Duintjer Tebbens, Gérard Meurant

Published in: Numerical Algorithms | Issue 4/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The paper gives a characterization of all linear systems such that when restarted GMRES is applied, prescribed admissible residual norms and (harmonic) Ritz values for all iterations inside the individual cycles are generated. Additionally, the system matrices can have any nonzero eigenvalues. The total number of GMRES iterations inside all cycles considered is assumed to be smaller than the system size. It is shown that stagnation at the end of a restart cycle must be mirrored at the beginning of the next cycle and that this is the only restriction for prescribed residual norms of restarted GMRES. The relation between prescribed residual norms of restarted GMRES and those of the corresponding full GMRES process is studied and linear systems are given where full and restarted GMRES give the same convergence history.

previous article FDEMtools: a MATLAB package for FDEM data inversion

next article On prescribing the convergence behavior of the conjugate gradient algorithm

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Arioli, M., Pták, V., Strakoš, Z.: Krylov sequences of maximal length and convergence of GMRES. BIT 38(4), 636–643 (1998)MathSciNetMATH

Brown, P.N.: A theoretical comparison of the Arnoldi and GMRES algorithms. SIAM J. Sci. Statist. Comput. 12(1), 58–78 (1991)MathSciNetMATH

Chapman, A., Saad, Y.: Deflated and augmented Krylov subspace techniques. Numer. Linear Algebra Appl. 4(1), 43–66 (1997)MathSciNetMATH

De Sturler, E.: Truncation strategies for optimal Krylov subspace methods. SIAM J. Numer. Anal. 36(3), 864–889 (1999)MathSciNetMATH

Du, K., Duintjer Tebbens, J., Meurant, G.: Any admissible harmonic Ritz value set is possible for GMRES. Electron. Trans. Numer. Anal. 47(SI), 37–56 (2017)MathSciNetMATH

Duintjer Tebbens, J., Meurant, G.: Any Ritz value behavior is possible for Arnoldi and for GMRES. SIAM J. Matrix Anal. Appl. 33(3), 958–978 (2012)MathSciNetMATH

Duintjer Tebbens, J., Meurant, G.: Prescribing the behavior of early terminating GMRES and Arnoldi iterations. Num. Algor. 65(1), 69–90 (2014)MathSciNetMATH

Duintjer Tebbens, J., Meurant, G.: On the convergence of Q-OR and Q-MR Krylov methods for solving nonsymmetric linear systems. BIT 56(1), 77–97 (2016)MathSciNetMATH

Duintjer Tebbens, J., Meurant, G., Sadok, H., Strakoš, Z.: On investigating GMRES convergence using unitary matrices. Lin. Alg. Appl. 450, 83–107 (2014)MathSciNetMATH

10.

Eiermann, M., Ernst, O.G.: Geometric aspects of the theory of Krylov subspace methods. Acta Numer. 10, 251–312 (2001)MathSciNetMATH

11.

Eiermann, M., Ernst, O.G., Schneider, O.: Analysis of acceleration strategies for restarted minimal residual methods. J. Comput. Appl. Math. 123(1–2), 261–292 (2000)MathSciNetMATH

12.

Elman, H.: Iterative Methods for Large Sparse Nonsymmetric Systems of Linear Equations. PhD thesis. Department of Computer Science. Yale University, New Haven (1982)

13.

Embree, M.: The tortoise and the hare restart GMRES. SIAM Rev. 45(2), 259–266 (2003)MathSciNetMATH

14.

Faber, V., Liesen, J., Tichý, P.: The Faber-Manteuffel theorem for linear operators. SIAM J. Numer. Anal. 46(3), 1323–1337 (2008)MathSciNetMATH

15.

Faber, V., Manteuffel, T.: Necessary and sufficient conditions for the existence of a conjugate gradient method. SIAM J. Numer. Anal. 21(2), 352–362 (1984)MathSciNetMATH

16.

Freund, R.W., Nachtigal, N.M.: QMR: A quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60(3), 315–339 (1991)MathSciNetMATH

17.

Gaul, A., Gutknecht, M.H., Liesen, J., Nabben, R.: A framework for deflated and augmented Krylov subspace methods. SIAM J. Matrix Anal. Appl. 34 (2), 495–518 (2013)MathSciNetMATH

18.

Greenbaum, A., Pták, V., Strakoš, Z.: Any nonincreasing convergence curve is possible for GMRES. SIAM J. Matrix Anal. Appl. 17(3), 465–469 (1996)MathSciNetMATH

19.

Greenbaum, A., Strakoš, Z.: Matrices that generate the same Krylov residual spaces. In: Recent Advances in Iterative Methods, IMA Vol. Math. Appl., vol. 60, pp 95–118. Springer, New York (1994)

20.

Liesen, J., Strakoš, Z.: GMRES convergence analysis for a convection-diffusion model problem. SIAM J. Sci. Comput. 26(6), 1989–2009 (2005). (electronic)MathSciNetMATH

21.

Liesen, J., Strakoš, Z.: Krylov Subspace Methods, Principles and Analysis. Numerical Mathematics and Scientific Computation. Oxford University Press, Oxford (2013)MATH

22.

Meurant, G.: Necessary and sufficient conditions for GMRES complete and partial stagnation. Submitted

23.

Meurant, G., Duintjer Tebbens, J.: The role eigenvalues play in forming GMRES residual norms with non-normal matrices. Numer. Algor. 68, 143–165 (2015)MathSciNetMATH

24.

Morgan, R.B.: A restarted GMRES method augmented with eigenvectors. SIAM J. Matrix Anal. Appl. 16(4), 1154–1171 (1995)MathSciNetMATH

25.

Morgan, R.B.: Implicitly restarted GMRES and Arnoldi methods for nonsymmetric systems of equations. SIAM J. Matrix Anal. Appl. 21(4), 1112–1135 (2000)MathSciNetMATH

26.

Morgan, R.B.: GMRES with deflated restarting. SIAM J. Sci. Comput. 24(1), 20–37 (2002)MathSciNetMATH

27.

Nachtigal, N.M., Reichel, L., Trefethen, L.N.: A hybrid GMRES algorithm for nonsymmetric linear systems. SIAM J. Matrix Anal. Appl. 13(3), 796–825 (1992)MathSciNetMATH

28.

Parlett, B., Strang, G.: Matrices with prescribed Ritz values. Linear Algebra Appl. 428(7), 1725–1739 (2008)MathSciNetMATH

29.

Saad, Y.: Analysis of augmented Krylov subspace methods. SIAM J. Matrix Anal. Appl. 18(2), 435–449 (1997)MathSciNetMATH

30.

Saad, Y., Schultz, M.H.: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7(3), 856–869 (1986)MathSciNetMATH

31.

Schweitzer, M.: Any finite convergence curve is possible in the initial iterations of restarted FOM. Electron. Trans. Numer. Anal. 45, 133–145 (2016)MathSciNetMATH

32.

Simoncini, V.: On the convergence of restarted Krylov subspace methods. SIAM J. Matrix Anal. Appl. 22(2), 430–452 (2000)MathSciNetMATH

33.

Simoncini, V., Szyld, D.B.: New conditions for non-stagnation of minimal residual methods. Numer. Math. 109(3), 477–487 (2008)MathSciNetMATH

34.

de Surler, E.: Personal communication (2013)

35.

Vecharynski, E., Langou, J.: The cycle-convergence of restarted GMRES for normal matrices is sublinear. SIAM J. Sci. Comput. 32(1), 186–196 (2010)MathSciNetMATH

36.

Vecharynski, E., Langou, J.: Any admissible cycle-convergence behavior is possible for restarted GMRES at its initial cycles. Num. Lin. Algebr. Appl. 18, 499–511 (2011)MathSciNetMATH

37.

Zavorin, I., O’Leary, D.P., Elman, H.: Complete stagnation of GMRES. Linear Algebra Appl. 367, 165–183 (2003)MathSciNetMATH

38.

Zhong, B., Morgan, R.B.: Complementary cycles of restarted GMRES. Numer. Linear Algebra Appl. 15(6), 559–571 (2008)MathSciNetMATH

39.

Zítko, J.: Generalization of convergence conditions for a restarted GMRES. Numer. Linear Algebra Appl. 7(3), 117–131 (2000)MathSciNetMATH

40.

Zítko, J.: Some remarks on the restarted and augmented GMRES method. Electron. Trans. Numer. Anal. 31, 221–227 (2008)MathSciNetMATH

Title: On the residual norms, the Ritz values and the harmonic Ritz values that can be generated by restarted GMRES
Authors: Jurjen Duintjer Tebbens
Gérard Meurant
Publication date: 12-12-2019
Publisher: Springer US
Published in: Numerical Algorithms / Issue 4/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-019-00846-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2020

Computation of energy eigenvalues of the anharmonic Coulombic potential with irregular singularities

The simpler block CMRH method for linear systems

Identification of the source function for a seawater intrusion problem in unconfined aquifer

A variational method for solving two-dimensional Bratu’s problem

Special volume on mathematical modeling with applications

FDEMtools: a MATLAB package for FDEM data inversion

Premium Partner