LemmaStatement: AI-adaptedProof: 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 and idealized span of completed Parareal sweeps

Statement

Suppose initialization and all $K \geq 0$ sweeps of Finite-budget Parareal correction sweeps complete successfully. They make $K N$ fine calls and $(K + 1) N$ coarse calls. In an accounting model with constant nonnegative call costs $c_{F}, c_{G}$ , $P$ processors for a positive integer $P$ , fine calls scheduled without idle time in batches of $P$ except possibly the last, serial coarse calls, and additive synchronization cost $τ_{s y n c} \geq 0$ per sweep, their modeled work and span are respectively $W = K N c_{F} + (K + 1) N c_{G} + K τ_{s y n c}, S = N c_{G} + K (⌈ N / P ⌉ c_{F} + N c_{G} + τ_{s y n c}) .$ This model excludes vector arithmetic, storage, certificate verification and any overhead other than the declared synchronization cost. It gives no measured speedup guarantee.

Facts & Assumptions

Given: Successful completion and the accounting model in the Statement; $N \geq 1$ and $K \geq 0$ are integers.

[F1]

Finite-budget Parareal correction sweeps initializes one serial coarse row, then evaluates all $N$ fine calls and $N$ new coarse calls per sweep, reusing the preceding row's stored coarse values.

Proof

1.1givenF1algebra

Initialization makes $N$ coarse calls. Each of the $K$ sweeps in [F1] makes $N$ fine calls and $N$ new coarse calls, so the totals are $K N$ and $(K + 1) N$ . Multiplying by the stipulated costs and adding $K$ synchronization charges gives $W$ .

2.1givenF1step 1.1algebra∎

Each fine phase has $N$ independent equal-cost calls. Filling each batch except possibly the last gives $⌈ N / P ⌉$ batches, taking $⌈ N / P ⌉ c_{F}$ without idle time. Initialization takes $N c_{G}$ , and each sweep has this fine phase followed by $N$ serial coarse calls and one synchronization charge. Adding these sequential phases gives $S$ , including $K = 0$ and zero call costs.

Depends on

Finite-budget Parareal correction sweeps

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

2 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

R. D. Falgout et al., Parallel Time Integration with Multigrid (standard reference, not scraped)