ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

V- and W-cycle work under two-dimensional four-to-one coarsening

Example

Assume a two-dimensional hierarchy with levels $j = 0, \dots, L$ of sizes $N_{j} = 4^{j}$ , so the finest level has $N = N_{L} = 4^{L}$ unknowns and each coarsening step reduces the size by four. Suppose each level has constant $c > 0$ work per unknown, the base solve has bounded positive cost, and the cycle is as in Finite recursive Galerkin V- and W-cycle for an SPD hierarchy. The V-cycle has one coarse call; the W-cycle has two. Both have $Θ (N)$ arithmetic work under these hypotheses, with different geometric sums.

Facts & Assumptions

Given: Integer $L \geq 1$ , level sizes $N_{j} = 4^{j}$ for $0 \leq j \leq L$ , $N = N_{L} = 4^{L}$ , per-level work $c N_{j}$ with $c > 0$ , a bounded positive coarsest solve, and the V/W call counts $γ = 1, 2$ .

[F1]

Work recurrence for fixed-coarsening multigrid cycles in all three regimes: for $q = 2^{d} = 4$ , work is $Θ (N)$ when $γ < 4$ .

Verification

1.1givenF1algebra

For the V-cycle, $T_{V} (N) = c N + T_{V} (N / 4)$ . Repeated substitution gives $T_{V} (N) = c N \sum_{r = 0}^{L - 1} 4^{- r} + T_{V} (1) .$ The sum lies between $1$ and $4 / 3$ , and $T_{V} (1) = Θ (1)$ , so $T_{V} (N) = Θ (N)$ . This is also the $γ = 1 < 4$ case of [F1].

2.1givenF1algebra∎

For the W-cycle, $T_{W} (N) = c N + 2 T_{W} (N / 4)$ , so $T_{W} (N) = c N \sum_{r = 0}^{L - 1} 2^{- r} + 2^{L} T_{W} (1) .$ The sum lies between $1$ and $2$ , while $2^{L} = \sqrt{N}$ ; consequently both terms are $O (N)$ and the first is a positive $c N$ lower bound. Hence $T_{W} (N) = Θ (N)$ , agreeing with [F1] because $γ = 2 < 4$ .

Depends on

Used by

Nothing in the library uses this result yet.

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

Susanne C. Brenner and L. Ridgway Scott, The Mathematical Theory of Finite Element Methods, 3rd ed., Chapter 6 (standard reference, not scraped)
Numerical Methods II, University of Heidelberg lecture notes, Chapter 10 (standard reference, not scraped)