LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

A linear Galerkin V/W cycle is translation-covariant

Statement

For the linear Galerkin V/W-cycle procedure of Finite recursive Galerkin V- and W-cycle for an SPD hierarchy, on any level $j$ and for all $x, a, b \in R^{n_{j}}$ , $Cycle (j, x + a, b + A_{j} a) = a + Cycle (j, x, b) .$ The identity is in exact arithmetic and uses the same hierarchy, smoothing matrices, sweep counts, and cycle count on both sides.

Facts & Assumptions

Given: A finite SPD Galerkin hierarchy, residual-correction pre/post updates, fixed finite sweep and cycle counts, and the exact coarsest solve from Finite recursive Galerkin V- and W-cycle for an SPD hierarchy.

[F1]

Finite recursive Galerkin V- and W-cycle for an SPD hierarchy: a noncoarsest call pre-smooths by $x \leftarrow x + K^{p r e} (b - A_{j} x)$ , restricts $r = b - A_{j} x$ , starts the coarse correction at $e = 0$ , makes recursive calls with right side $P_{j}^{T} r$ , prolongs by $P_{j} e$ , and post-smooths by the same residual-correction form.

Proof

1.1givenF1algebra

At level $j = 0$ , [F1] returns $A_{0}^{- 1} b$ . Since $A_{0}$ is invertible, $A_{0}^{- 1} (b + A_{0} a) = A_{0}^{- 1} b + a,$ so the identity holds at the base level.

1.2givenF1algebra

At a noncoarsest level, if the current state is shifted from $x$ to $x + a$ and the right side from $b$ to $b + A_{j} a$ , then the residual is unchanged because $(b + A_{j} a) - A_{j} (x + a) = b - A_{j} x$ . Each pre-smoothing update in [F1] therefore preserves the shift by $a$ and gives the same fine residual in the two executions.

2.1F1step 1.2algebra

With identical fine residuals, both executions start the coarse correction at $e = 0$ and call the same deterministic recursive procedure with the same right side $P_{j}^{T} r$ . Thus every call returns the same coarse correction $e$ , including every repeated W-cycle call. Prolongation adds the same $P_{j} e$ to both shifted states, and the post-smoothing residuals are again identical, so every post-update preserves the shift.

3.1step 1.1step 1.2step 2.1∎

The base calculation and the noncoarsest calculation establish the stated identity for every level of the finite hierarchy.

Depends on

Finite recursive Galerkin V- and W-cycle for an SPD hierarchy

Used by

Linear FAS exactly reduces to a Galerkin correction V/W cycle Theorem

Dependency tree · two levels

5 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

William L. Briggs, Van Emden Henson, and Steve F. McCormick, A Multigrid Tutorial, 2nd ed., Chapter 6 (standard reference, not scraped)
Harald van Brummelen, Basics of Multigrid Methods, SINTEF winter-school lecture notes (standard reference, not scraped)
Van Emden Henson, Multigrid Methods for Nonlinear Problems: An Overview, UCRL-JC-150259 (standard reference, not scraped)