On the residual norms, the Ritz values and the harmonic Ritz values that can be generated by restarted GMRES
type: Item
instance of: scholarly article
title: On the residual norms, the Ritz values and the harmonic Ritz values that can be generated by restarted GMRES
zbMATH Open document ID: 1444.65011
author: Jurjen Duintjer Tebbens
author: G. Meurant
published in: Numerical Algorithms
publication date: 2020-07-15T00:00:00Z
review text: It is known that in the method of Krylov for solving the linear system \[ Ax = b,\: A\in \mathbb{C}^{n \times n}, \: b\in \mathbb{C}^n \] with a nonsingular, non-Hermitian, sparse and possibly very large matrix \(A\), the \(k\)-th iterate \(x_k\) minimizes the norm of the residual vector \(r_k=b-Ax_k\) over all vectors in the \(k\)-th Krylov subspace \(\mathrm{span}\{r_0, Ar_0,\ldots ,A^{k-1}r_0\}\), leading to nonincreasing residual norms, and the employed basis must in general be generated with long recurrences. In the article, the authors give 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. With an enviable technique, the authors show that stagnation at the end of a restart cycle must be mirrored at the beginning of the next cycle, which is the only restriction for prescribed residual norms of restarted GMRES. Section~4 addresses the relation of the constructed linear systems with full GMRES. The paper deals with some interesting unsolved problems that may be of interest to specialists working in this area of computational mathematics.
reviewed by: Nikolay Kyurkchiev
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F50
zbMATH DE Number: 7221102
zbMATH Keywords: restarted GMRES
zbMATH Keywords: Ritz values
zbMATH Keywords: GMRES stagnation
zbMATH Keywords: prescribed convergence
MaRDI profile type: Publication
full work available at URL: s11075-019-00846-z
OpenAlex ID: W2994740981
cites work: Krylov sequences of maximal length and convergence of GMRES
cites work: A Theoretical Comparison of the Arnoldi and GMRES Algorithms
cites work: Deflated and Augmented Krylov Subspace Techniques
cites work: Truncation Strategies for Optimal Krylov Subspace Methods
cites work: Any admissible harmonic Ritz value set is possible for GMRES
cites work: Any Ritz Value Behavior Is Possible for Arnoldi and for GMRES
cites work: Prescribing the behavior of early terminating GMRES and Arnoldi iterations
cites work: On the convergence of Q-OR and Q-MR Krylov methods for solving nonsymmetric linear systems
cites work: On investigating GMRES convergence using unitary matrices
cites work: Geometric aspects of the theory of Krylov subspace methods
cites work: Analysis of acceleration strategies for restarted minimal residual methods
cites work: The Tortoise and the Hare Restart GMRES
cites work: The Faber–Manteuffel Theorem for Linear Operators
cites work: Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method
cites work: QMR: A quasi-minimal residual method for non-Hermitian linear systems
cites work: A framework for deflated and augmented Krylov subspace methods
cites work: Any Nonincreasing Convergence Curve is Possible for GMRES
cites work: Q4309410
cites work: GMRES Convergence Analysis for a Convection-Diffusion Model Problem
cites work: Q4649579
cites work: Necessary and sufficient conditions for GMRES complete and partial stagnation
cites work: The role eigenvalues play in forming GMRES residual norms with non-normal matrices
cites work: A Restarted GMRES Method Augmented with Eigenvectors
cites work: Implicitly Restarted GMRES and Arnoldi Methods for Nonsymmetric Systems of Equations
cites work: GMRES with Deflated Restarting
cites work: A Hybrid GMRES Algorithm for Nonsymmetric Linear Systems
cites work: Matrices with prescribed Ritz values
cites work: Analysis of Augmented Krylov Subspace Methods
cites work: GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
cites work: Any finite convergence curve is possible in the initial iterations of restarted FOM
cites work: On the convergence of restarted Krylov subspace methods
cites work: New conditions for non-stagnation of minimal residual methods
cites work: The Cycle-Convergence of Restarted GMRES for Normal Matrices Is Sublinear
cites work: Any admissible cycle-convergence behavior is possible for restarted GMRES at its initial cycles.
cites work: Complete stagnation of GMRES
cites work: Complementary cycles of restarted GMRES
cites work: Generalization of convergence conditions for a restarted GMRES
cites work: Some remarks on the restarted and augmented GMRES method
Wikidata QID: Q126578171
DOI: 10.1007/S11075-019-00846-Z
description: scientific article; zbMATH DE number 7221102