Analysis of GMRES for Low-Rank and Small-Norm Perturbations of the Identity Matrix

arXiv2210.12053MaRDI QIDQ6414697FDOQ6414697

Authors: Arielle Carr, E. de Sturler, Mark Embree 

Publication date: 21 October 2022

Abstract: In many applications, linear systems arise where the coefficient matrix takes the special form $$, where $$ is the identity matrix of dimension $n$, $$, and $$. GMRES convergence rates for linear systems with coefficient matrices of the forms $$ and $$ are guaranteed by well-known theory, but only relatively weak convergence bounds specific to matrices of the form $$ currently exist. In this paper, we explore the convergence properties of linear systems with such coefficient matrices by considering the pseudospectrum of $$. We derive a bound for the GMRES residual in terms of $epsilon$ when approximately solving the linear system $$ and identify the eigenvalues of $$ that are sensitive to perturbation. In particular, while a clustered spectrum away from the origin is often a good indicator of fast GMRES convergence, that convergence may be slow when some of those eigenvalues are ill-conditioned. We show there can be at most $2p$ eigenvalues of $$ that are sensitive to small perturbations. We present numerical results when using GMRES to solve a sequence of linear systems of the form $$ that arise from the application of Broyden's method to solve a nonlinear partial differential equation.

This page was built for publication: Analysis of GMRES for Low-Rank and Small-Norm Perturbations of the Identity Matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414697)