ExampleConstruction: AI-adaptedVerification: 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 can need more cycles than unrestarted GMRES on the same system

Example

For the system

$A = (\begin{array}{cc} 0 & 2 \\ 1 & 1 \end{array}), b = e_{1}, x_{0} = 0,$

full GMRES solves exactly in at most two steps because the matrix is $2 \times 2$ , but restarted GMRES $(1)$ stagnates immediately: every one-step cycle returns the same iterate $x = 0$ .

Facts & Assumptions

Given: The system from the previous counterexample.

[L1]

Restarted GMRES keeps cyclewise minimization but need not inherit the full unrestarted termination guarantee (Restarted GMRES preserves cyclewise residual minimization but loses the unrestarted finite-termination guarantee).

Verification

technique · direct

1.1

The previous calculation gives the one-step GMRES minimizer $x_{1} = 0$ , so a GMRES $(1)$ cycle starting from $x_{0} = 0$ ends where it started. Restarting therefore reproduces the same residual $r_{0} = e_{1}$ and the same one-step problem, so every cycle returns $0$ again.

L1algebra

2.1

By contrast, unrestarted GMRES on an invertible $2 \times 2$ system reaches the exact solution by step $2$ . Thus restart length $1$ preserves the cyclewise minimization promised by [L1] but discards the information needed for the full method's finite termination.

L1step 1.1algebra∎

Depends on

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

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

4 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)