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.