TheoremStatement: Literature-sourcedProof: 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.

Work recurrence for fixed-coarsening multigrid cycles in all three regimes

Statement

For any finite Galerkin hierarchy and parameters admitted by Finite recursive Galerkin V- and W-cycle for an SPD hierarchy, every invocation of the recursive procedure terminates. For the work estimate, fix an integer $d \geq 1$ and let $L \geq 0$ range over integers. Set $q = 2^{d}$ , and let the hierarchy have sizes $N_{j} = q^{j}$ for $0 \leq j \leq L$ , so its finest size is $N = N_{L} = q^{L}$ and each coarsening step divides the size by the fixed factor $q$ . Suppose each level with $N_{j}$ unknowns has $c N_{j}$ arithmetic work outside recursion for a fixed $c > 0$ , the base solve at $N_{0} = 1$ has fixed bounded positive cost, and each cycle makes a fixed positive integer $γ$ recursive calls. With $d, c, γ$ fixed, the work recurrence

$T (N) = c N + γ T (N / q)$

has order $Θ (N)$ when $γ < q$ , $Θ (N \log N)$ when $γ = q$ , and $Θ (N^{\log_{q} γ})$ when $γ > q$ , as $L \to \infty$ . These are arithmetic-work bounds conditional on the stated uniform per-level cost and coarsening assumptions. They do not imply convergence or include setup cost.

Facts & Assumptions

Given: A finite Galerkin hierarchy and parameters admitted by Finite recursive Galerkin V- and W-cycle for an SPD hierarchy. For the work estimate, a fixed integer $d \geq 1$ , integer $L \geq 0$ , $q = 2^{d}$ , level sizes $N_{j} = q^{j}$ for $0 \leq j \leq L$ , $N = N_{L} = q^{L}$ , a fixed $c > 0$ , fixed positive integer $γ$ , and base cost $T (1) = Θ (1)$ .

[F1]

Finite recursive Galerkin V- and W-cycle for an SPD hierarchy: the base branch solves $A_{0} z = b$ exactly; at a positive level, the procedure uses finitely many pre- and post-sweeps and makes exactly $γ$ recursive calls at the next coarser level.

[F2]

Every real symmetric positive-definite matrix is invertible, so the base system has a unique exact solution (For Hermitian positive-definite $A$ , the exact solution of $A x = b$ is the unique minimizer of the quadratic energy).

Proof

1.1givenF1F2induction

For any admissible finite hierarchy, at level $j = 0$ the matrix $A_{0}$ is real symmetric positive definite, so [F2] gives a unique solution and the base branch is defined. Inductively, if every call at level $j - 1$ terminates, then a call at level $j$ terminates: its pre- and post-sweep counts are finite, and its loop makes the finite number $γ$ of terminating calls at level $j - 1$ . Hence every invocation on every admissible finite hierarchy terminates.

2.1givenF1step 1.1inductionalgebra

Repeated substitution in the recurrence gives $T (N) = c N \sum_{r = 0}^{L - 1} (γ / q)^{r} + γ^{L} T (1) .$ For $L = 0$ , the sum is empty and this is the base cost; for $L + 1$ , substituting $T (N / q)$ adds the term $c N (γ / q)^{L}$ and leaves the base term $γ^{L + 1} T (1)$ , proving the formula by induction on $L$ .

3.1step 2.1algebra

If $γ < q$ , the ratio $γ / q < 1$ , so the finite geometric sum is bounded above and below by positive constants independent of $L$ . Also $γ^{L} = N^{\log_{q} γ} = o (N)$ , while $c N$ is a lower bound. Hence $T (N) = Θ (N)$ .

3.2step 2.1algebra

If $γ = q$ , the sum in step 2.1 is $L$ , and $γ^{L} T (1) = N T (1) = Θ (N)$ . Since $L = \log_{q} N$ , this gives $T (N) = Θ (N \log N)$ .

3.3step 2.1algebra

If $γ > q$ , the geometric sum is $Θ ((γ / q)^{L})$ . Thus the first term in step 2.1 is $Θ (N (γ / q)^{L}) = Θ (γ^{L}) = Θ (N^{\log_{q} γ})$ ; the base term has the same order. Therefore $T (N) = Θ (N^{\log_{q} γ})$ .

4.1givenF1step 1.1step 2.1∎

The recurrence counts only the per-level cycle work stated in the hypotheses and the recursive calls in [F1]. It contains no setup, floating-point error, or convergence estimate.

Depends on

Used by

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

Cited to discharge well-definedness by Finite recursive Galerkin V- and W-cycle for an SPD hierarchy.

Dependency tree · two levels

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