Once upon a time, we considered using simple GMRES to fix an $$LU$$ factorization perturbed along the diagonal. More specifically, you sometimes need to perturb a tiny pivot when you’ve chosen them statically before factorization.

The previous SuperLU perturbation heuristics sometimes produced perturbations too large for iterative refinement to fix. Applying a few steps of non-preconditioned GMRES appeared to work, although it’s more expensive.

However, non-preconditioned GMRES cannot fix an arbitrary perturbation in few steps. Consider an $$N\times N$$ unit-entry, lower-bidiagonal matrix \begin{equation*} A = \left[\begin{array}{lc} 1 & 0 & 0 & & & 0 \newline 1 & 1 & 0 & \cdots & & \newline 0 & 1 & 1 & & & \newline & \vdots & & \ddots& & \newline & & & & 1 & 0 \newline 0 & & & & 1 & 1 \end{array}\right], \end{equation*} and a system $$A x = b$$ with $$b = [1; -1; 1; -1; \ldots]$$. The true solution is $$x = [1; 2; 3; \ldots]$$.

Perturb the first diagonal entry of $$A$$ to $$\tilde{A}$$ and every component of the computed solution $$y = \tilde{A}^{-1} b$$ differs from $$x$$, but the residual $$r$$ is non-zero only in its first entry. (You can play with the entries to render all calculations exact; I just don’t have the worked exact example handy.)

The first iteration of GMRES searches the space $$\operatorname{span} \{ r \}$$ for an improvement to the computed $$y$$. That alters only the first component of $$y$$. The second iteration searches $$\operatorname{span} \{ r, A r \}$$. Because $$A$$ is upper Hessenberg, this space only affects the first two components of $$y$$. In general, the $$i$$th iteration of GMRES only affects the first $$i$$ components of the computed solution $$y$$.

The computed $$y$$ differs from the true solution $$x$$ in every component, so plain GMRES requires $$N$$ iterations to fix a single perturbation.

If you use the perturbed factorization as a preconditioner, however, the behavior is more difficult to analyze. I don’t have a clean example of failing behavior handy, nor have I proven that it works for sufficiently small perturbations. Definitely something to consider further. Avron, Ng, and Toledo (2009) show that preconditioning with $$R$$ in a perturbed $$QR$$ works for least-squares problems.