PropositionStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-31

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Restarted GMRES preserves cyclewise residual minimization but loses the unrestarted finite-termination guarantee

Statement

In restarted GMRES $(m)$ , each cycle output $x^{(j + 1)}$ minimizes the residual norm over the current affine space $x^{(j)} + K_{m} (A, r^{(j)})$ . However, after restarting one no longer minimizes over the full unrestarted space $x_{0} + K_{k} (A, r_{0})$ for large $k$ , so the unrestarted finite-termination theorem does not carry over automatically.

Facts & Assumptions

Given: A restarted GMRES $(m)$ cycle from $x^{(j)}$ with residual $r^{(j)} = b - A x^{(j)}$ .

[F1]

Restarted GMRES $(m)$ is defined by running ordinary GMRES for $m$ steps from the current iterate and then restarting from the cycle output (Restarted GMRES $(m)$ as repeated GMRES cycles on fixed-size Krylov spaces).

[L1]

Ordinary GMRES minimizes the residual norm over its affine Krylov space (GMRES minimizes the residual norm over the affine Krylov space $x_{0} + K_{m} (A, r_{0})$ ).

[L2]

Unrestarted finite termination uses the fact that the exact solution lies in one large affine Krylov space built from the original residual (In exact arithmetic, unrestarted GMRES terminates no later than the relative grade).

Proof

technique · direct

1.1

By [F1], the $(j + 1)$ st restarted iterate is obtained by applying ordinary GMRES to the system with initial guess $x^{(j)}$ and initial residual $r^{(j)}$ . Therefore [L1] gives $∥ b - A x^{(j + 1)} ∥_{2} = \min_{x \in x^{(j)} + K_{m} (A, r^{(j)})} ∥ b - A x ∥_{2} .$

F1L1

2.1

The unrestarted theorem [L2] uses the single expanding family $x_{0} + K_{k} (A, r_{0})$ . After a restart, [F1] replaces that space by the new cycle space $x^{(j)} + K_{m} (A, r^{(j)})$ , which need not contain the exact solution even when some larger unrestarted space would. Hence cyclewise minimization remains true, but the unrestarted finite-termination guarantee is no longer a formal consequence after restart.

F1L2step 1.1∎

Depends on

Used by

Restarted GMRES can need more cycles than unrestarted GMRES on the same system Example

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yousef Saad, CSCI 8314 Set 14: Krylov subspace methods (continued); Practical variants: restarting and truncating; Hermitian case: The Lanczos algorithm; Conjugate gradients (standard reference, not scraped)