ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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.

Matrix-free GMRES accesses the matrix only through applications of the operator to vectors

Example

Define a linear operator on $R^{4}$ by

$T (v_{1}, v_{2}, v_{3}, v_{4}) = (2 v_{1} - v_{2}, - v_{1} + 2 v_{2} - v_{3}, - v_{2} + 2 v_{3} - v_{4}, - v_{3} + 2 v_{4}) .$

Starting from $b = e_{1}$ , the first Krylov vectors are

$b = e_{1}, T b = (2, - 1, 0, 0), T^{2} b = (5, - 4, 1, 0) .$

So Arnoldi and GMRES can begin from repeated calls to the routine $v \mapsto T (v)$ , without ever storing the full tridiagonal matrix of $T$ .

Facts & Assumptions

Given: The operator $T$ above and the start vector $b = e_{1}$ .

[F1]

In the matrix-free model, Krylov methods need only operator applications, vector updates, inner products, and norms (The matrix-free access model for Krylov methods).

[F2]

Restarted GMRES is built from ordinary GMRES cycles on such Krylov spaces (Restarted GMRES $(m)$ as repeated GMRES cycles on fixed-size Krylov spaces).

Verification

technique · direct

1.1

Direct evaluation of the operator routine gives the displayed vectors $T b$ and $T^{2} b$ . Those are exactly the data from which the first Krylov spaces and the first Arnoldi orthogonalization steps are formed.

F1algebra

2.1

No entrywise matrix storage was used in step 1.1: only the map $v \mapsto T (v)$ , vector arithmetic, and inner products are needed. Therefore this sparse example fits the matrix-free access model [F1], and restarted cycles [F2] use the same access pattern on each new residual.

F1F2step 1.1∎

Depends on

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 13: Krylov subspace methods; Introduction; Krylov subspaces; Gram-Schmidt process (review); The Arnoldi process; FOM and GMRES (standard reference, not scraped)