Parallel in time parareal and mgrit

Let $d,N\ge 1$, let $X={\mathbb{R}}^d$, and fix macro times $t_0<t_1<\cdots <t_N$. A fine/coarse propagator pair is a pair of deterministic maps $F_n:D_n^F\to X$ and $G_n:D_n^G\to X$, for each $0\le n<N$, where $D_n^F,D_n^G\subseteq X$ are their admitted input sets. Both maps advance a state across the same interval $[t_n,t_{n+1}]$. The labels fine and coarse identify the two roles chosen by the user; they assert no accuracy, stability, cost, or convergence property.

For an initial state $x_0\in X$, whenever every call succeeds, the sequential fine trajectory is the finite sequence $x_{n+1}=F_n(x_n)$, and the sequential coarse trajectory is defined by replacing each $F_n$ with $G_n$. A partially defined map is unavailable outside its admitted set; a failed stage evaluation or an unavailable implicit branch is a propagation failure, not a numerical value.

A canonical ODE instantiation uses the explicit Runge–Kutta stage map of Explicit Runge–Kutta tableaus, stage maps, and failure status for $r\ge 1$ fine substeps of size $(t_{n+1}-t_n)\mathrm{/}r$, composed in order to form $F_n$. A coarse backward Euler value is an endpoint $z$ satisfying the equation in Backward Euler step equation and algebraic residual over the full macro interval. Its branch selector is part of the input and must select exactly one admissible root for each admitted start state; if no such selected root exists, the coarse map is unavailable. The backward Euler definition alone asserts neither root existence nor uniqueness.

This definition distinguishes the sequential fine trajectory from samples of an exact ODE solution. Any estimate of the fine method's error relative to that exact solution is a separate obligation.

Input: an admissible propagator pair from Fine and coarse propagators on a common macro grid, initial state $x_0$, number of macro intervals $N$, integer sweep budget $K\ge 0$, and optionally a wall-clock budget $\tau \ge 0$ and certificate data $(\mathcal{C},c,Q,V)$. Here $c\in \mathcal{C}$ is a supplied certificate, $Q$ is a declared predicate on completed rows, and $V(W,c)$ is a supplied deterministic verifier that terminates with a Boolean for every completed row $W$ and satisfies $V(W,c)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}\Rightarrow Q(W)$. Without certificate data, take $V$ to return false. Every map call is required to terminate with a state or declared failure. Each map call either returns one state or a declared failure status. The output contains every fully completed row of the table $U_n^k$ for $0\le k\le K$, the last completed endpoint when one exists, and a status. If initialization never completes, return an empty completed-row table and no endpoint.

Initialize $U_0^0=x_0$ and, in increasing order of $n$, set $U_{n+1}^0=G_n(U_n^0)$. Store the values $G_n(U_n^0)$. For each $k=0,\dots ,K-1$, set $U_0^{k+1}=x_0$. Evaluate $F_n(U_n^k)$ independently for all $n$; the stored $G_n(U_n^k)$ values are reused from the preceding row. Then, in increasing order of $n$, compute $G_n(U_n^{k+1})$ and set $U_{n+1}^{k+1}=G_n(U_n^{k+1})+F_n(U_n^k)-G_n(U_n^k)\mathrm{.}$ The fine calls in a sweep can run in parallel, while the corrected row is computed sequentially.

If a map call fails, return the last fully completed row and status propagation-failure; a prefix of the failed row may be reported separately but is not a completed iterate. If the time budget expires at a call boundary, return the last fully completed row and status budget-exhausted. When initialization and all $K$ requested sweeps finish, call $V$ on the final row and $c$ (or use false when no certificate was supplied). Return status converged if this returns true, certifying the declared predicate $Q$; otherwise return status budget-exhausted. Completion of the finite budget alone is not a convergence certificate.

For the exact-arithmetic recurrence, an update computed with inexact fine/coarse values or an inexact correction solve can be written as the displayed right-hand side plus a combined defect ${\eta }_n^{k+1}$. A residual tolerance alone does not bound that defect in forward error.

Let $d,N\ge 1$, let ${\mathrm{\Phi }}_i\in {\mathbb{R}}^{d\times d}$ for $1\le i\le N$, and let $u_0\in {\mathbb{R}}^d$ be fixed. The linear part of a fine propagator in Fine and coarse propagators on a common macro grid is represented by ${\mathrm{\Phi }}_i$. For forcing vectors $g_i\in {\mathbb{R}}^d$, write the fine recurrence as $u_i={\mathrm{\Phi }}_i{u}_{i-1}+g_i$. On the unknown vector $v=(v_1,\dots ,v_N)\in ({\mathbb{R}}^d{)}^N$, define $A_t$ by $(A_{t}v{)}_1=v_1$ and $(A_{t}v{)}_i=v_i-{\mathrm{\Phi }}_i{v}_{i-1}$ for $2\le i\le N$. With $b_1={\mathrm{\Phi }}_1{u}_0+g_1$ and $b_i=g_i$ for $i\ge 2$, the recurrence is exactly $A_{t}v=b$.

For a coarsening factor $m\ge 2$ dividing $N$, the coarse indices are $0,m,2m,\dots ,N$. Among unknowns, let $C=\{m,2m,\dots ,N\}$ and $F=\{1,\dots ,N\}\setminus C$. Reordering the unknown vector as $(v_F,v_C)$ gives $A_t=\left(\begin{array}{cc}{A}_{FF}& A_{FC}\\ A_{CF}& A_{CC}\end{array}\right)\mathrm{.}$ A practical coarse propagator ${\mathrm{\Psi }}_j$ on each interval is the linear subcase of the coarse maps $G_n$ in Fine and coarse propagators on a common macro grid; the exact coarse operator is determined by eliminating F-points and is not generally the same as this practical choice. This definition asserts no stability or convergence property.

For the exact-arithmetic recurrence in Finite-budget Parareal correction sweeps, let $x_0$ be the initial state and $x_{n+1}=F_n(x_n)$ its sequential fine trajectory. For every completed sweep $k$ and every $0\le n\le \min \{k,N\}$, $U_n^k=x_n$. Consequently, if the requested sweep budget $K\ge N$ is fully completed, the returned table contains the complete sequential fine trajectory in row $K$.

Let $x_{n+1}=F_n(x_n)$ be the sequential fine trajectory and let $U_n^k$ be the exact-arithmetic table from Finite-budget Parareal correction sweeps. Let $D\subseteq X$ contain every $x_n$ and every iterate used in the requested sweeps. Suppose constants $a,b,M\ge 0$ satisfy, for every $0\le n<N$ and $u,v\in D$, $\mathrm{\parallel }{G}_n(u)-G_n(v)\mathrm{\parallel }\le a\mathrm{\parallel }u-v\mathrm{\parallel },\mathrm{\parallel }(F_n-G_n)(u)-(F_n-G_n)(v)\mathrm{\parallel }\le b\mathrm{\parallel }u-v\mathrm{\parallel },$ and $\mathrm{\parallel }{U}_n^0-x_n\mathrm{\parallel }\le M$ for all $0\le n\le N$. Use $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ for the number of $k$-element subsets of an $n$-element set, set it to $0$ for $k>n$, and put $A=\max \{1,a\}$. Then for every node $0\le n\le N$ and completed sweep $k\ge 0$, $\mathrm{\parallel }{U}_n^k-x_n\mathrm{\parallel }\le M\left(\genfrac{}{}{0px}{}{n}{k}\right)A^n{b}^k,$ with $b^0=1$. The hypotheses include all comparison points; invariance of $D$ under $F_n,G_n$ alone does not ensure that corrected iterates stay in $D$.

For a fixed horizon $T=NH$, suppose $a\le 1+C_{a}H$, $b\le C_b{H}^{q+1}$ for constants $C_a,C_b\ge 0$ and integer $q\ge 1$, and one $M$ works uniformly as $N$ varies. Then, for each fixed $k\le N$, $\mathrm{\parallel }{U}_N^k-x_N\mathrm{\parallel }\le M(C_{b}T{)}^k\exp (C_{a}T)H^{qk}\mathrm{.}$ Thus the exact-solve error is $O(H^{qk})$ at each fixed iteration $k$ under these uniform assumptions. Neither estimate includes finite-solver error; that effect requires a separate update-defect analysis.

Use The all-at-once bidiagonal time operator and C/F points with $N=Jm$, $m\ge 2$, and its F/C partition. Both $A_t$ and $A_{FF}$ are invertible. Eliminating the F unknowns from $A_{t}v=b$ gives the coarse system with Schur complement $S=A_{CC}-A_{CF}{A}_{FF}^{-1}{A}_{FC}\mathrm{.}$ On coarse interval $j$, its recurrence is $u_{jm}-({\mathrm{\Phi }}_{jm}{\mathrm{\Phi }}_{jm-1}\cdots {\mathrm{\Phi }}_{(j-1)m+1})u_{(j-1)m}={\bar{g}}_j,$ where ${\bar{g}}_j={\sum }_{s=1}^m({\mathrm{\Phi }}_{jm}{\mathrm{\Phi }}_{jm-1}\cdots {\mathrm{\Phi }}_{(j-1)m+s+1})g_{(j-1)m+s},$ with an empty product defined to be the identity. If ${\mathrm{\Phi }}_i=\mathrm{\Phi }$ for every fine step, the exact coarse propagator is ${\mathrm{\Phi }}^m$.

Use the notation and Lipschitz hypotheses of A conditional binomial error bound for Parareal, with $A=\max \{1,a\}$. Let computed iterates $V_n^k\in D$ satisfy $V_0^k=x_0$, $\mathrm{\parallel }{V}_n^0-x_n\mathrm{\parallel }\le M$, and, for each requested correction, $\parallel V_{n+1}^{k+1}-[G_n(V_n^{k+1})+(F_n-G_n)(V_n^k)]\parallel \le \eta$ for a constant $\eta \ge 0$. Define $P_n^k=M\left(\genfrac{}{}{0px}{}{n}{k}\right)A^n{b}^k$ and a nonnegative forcing array by $R_0^k=0$, $R_n^0=0$, and $R_{n+1}^{k+1}=A{R}_n^{k+1}+b{R}_n^k+\eta \mathrm{.}$ Then $\mathrm{\parallel }{V}_n^k-x_n\mathrm{\parallel }\le P_n^k+R_n^k$ for every completed node and sweep.

The base envelope $M$ includes coarse-initialization error relative to the fine trajectory. The per-update defect $\eta$ must bound the actual combined effect of fine/coarse evaluation errors and correction-solve error; a residual tolerance alone supplies no forward-error bound.

Input: a linear fine-grid system $A_{t}u=b$ with $N\ge 1$ fine intervals as in The all-at-once bidiagonal time operator and C/F points, a coarsening factor $m\ge 2$ dividing $N$ and its C/F partition as in Eliminating F-points gives the exact coarse time operator, practical coarse propagators ${\mathrm{\Psi }}_j\in {\mathbb{R}}^{d\times d}$ for $1\le j\le N_c:=N\mathrm{/}m$, an initial fine-grid iterate $u_{\mathrm{i}\mathrm{n}}$, pre- and post-relaxation choices from $\{F,FCF\}$, a real-valued norm on the fine-grid residual space as in A norm on a real vector space, the induced metric, and the dictionary with the metric axioms, a nonnegative integer cycle budget $J_{\mathrm{c}\mathrm{y}\mathrm{c}}$, and a residual tolerance $\epsilon \ge 0$. The symbol $J_{\mathrm{c}\mathrm{y}\mathrm{c}}$ is the number of permitted cycles; the coarse-interval count is $N_c$ (the letter $J$ in Eliminating F-points gives the exact coarse time operator denotes that lemma's coarse-interval count). The output is the last iterate, its residual norm, the number of completed cycles, and status converged or budget-exhausted.

In F/C ordering define ideal interpolation $P$ and restriction $R$ by $P=\left[\begin{array}{c}-A_{FF}^{-1}{A}_{FC}\\ I_C\end{array}\right],R=\left[\begin{array}{cc}-A_{CF}{A}_{FF}^{-1}& I_C\end{array}\right]\mathrm{.}$

The exact coarse operator is the Schur complement $R{A}_{t}P=A_{CC}-A_{CF}{A}_{FF}^{-1}{A}_{FC}$ from Eliminating F-points gives the exact coarse time operator. The practical correction matrix $A_c$ has identity diagonal blocks and subdiagonal blocks $-{\mathrm{\Psi }}_j$ for $2\le j\le N_c$; its first row corresponds to the fixed zero initial correction $z_0=0$. For any right-hand side $\rho$, forward substitution uniquely solves $A_{c}z=\rho$ by setting $z_0=0$ and, in increasing order for $j=1,\dots ,N_c$, setting $z_j={\rho }_j+{\mathrm{\Psi }}_j{z}_{j-1}$. Thus $A_c$ is invertible even when an individual ${\mathrm{\Psi }}_j$ is singular.

Define the relaxations on $A_{t}u=b$ as follows. An F-relaxation holds every C-value fixed and, for each coarse interval $j=1,\dots ,N_c$, updates its F-indices $i=(j-1)m+1,\dots ,jm-1$ in increasing order: set $u_1=b_1$ if $i=1$, and otherwise set $u_i=b_i+{\mathrm{\Phi }}_i{u}_{i-1}$. Different coarse intervals have independent F-updates and may be processed in parallel. A C-relaxation holds every F-value fixed and, for $j=1,\dots ,N_c$ in increasing order, sets $u_{jm}=b_{jm}+{\mathrm{\Phi }}_{jm}{u}_{jm-1}$; these C-updates are independent because $m\ge 2$ and each predecessor is an F-index. An FCF-relaxation applies F-relaxation, then C-relaxation, then F-relaxation. Each relaxation is a finite linear update; write $S_{\mathrm{p}\mathrm{r}\mathrm{e}}$ and $S_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}$ for the error maps of the selected pre- and post-relaxations.

For one cycle from a current iterate $u$, apply the selected pre-relaxation; form $r=b-A_{t}u$ and $\rho =Rr$; solve $A_{c}z=\rho$ by the forward substitution above; correct $u\leftarrow u+Pz$; then apply the selected post-relaxation. The exact error-propagation matrix of this fixed cycle is $E=S_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}(I-P{A}_c^{-1}R{A}_t)S_{\mathrm{p}\mathrm{r}\mathrm{e}}\mathrm{.}$

Initialize $u^{(0)}=u_{\mathrm{i}\mathrm{n}}$ and compute $\mathrm{\parallel }b-A_t{u}^{(0)}\mathrm{\parallel }$. If this is at most $\epsilon$, return $u^{(0)}$, zero completed cycles, and status converged. Otherwise, for $j_{\mathrm{c}\mathrm{y}\mathrm{c}}=1,\dots ,J_{\mathrm{c}\mathrm{y}\mathrm{c}}$, perform one cycle, call the resulting iterate $u^{(j_{\mathrm{c}\mathrm{y}\mathrm{c}})}$, and compute $\mathrm{\parallel }b-A_t{u}^{(j_{\mathrm{c}\mathrm{y}\mathrm{c}})}\mathrm{\parallel }$. If this norm is at most $\epsilon$, return that iterate, $j_{\mathrm{c}\mathrm{y}\mathrm{c}}$ completed cycles, and status converged; if not, continue. If all $J_{\mathrm{c}\mathrm{y}\mathrm{c}}$ cycles finish without this condition (including when $J_{\mathrm{c}\mathrm{y}\mathrm{c}}=0$), return the last iterate, its residual norm, and status budget-exhausted. The matrix $E$ describes exact arithmetic and exact coarse solves; inexact solves contribute an update defect that needs its own bound.

Let $y:[0,T]\to {\mathbb{R}}^d$ solve a first-order initial-value problem as in First-order systems, initial value problems, and solutions on intervals, and let $x_n$ be the sequential fine trajectory from Fine and coarse propagators on a common macro grid on a grid $0=t_0<\cdots <t_N=T$. Suppose the inexact Parareal ledger gives $\mathrm{\parallel }{V}_n^K-x_n\mathrm{\parallel }\le P_n^K+R_n^K$, and suppose a separately established fine-method estimate gives $\mathrm{\parallel }{x}_n-y(t_n)\mathrm{\parallel }\le {\delta }_F$ for some ${\delta }_F\ge 0$ and every node. Then $\mathrm{\parallel }{V}_n^K-y(t_n)\mathrm{\parallel }\le P_n^K+R_n^K+{\delta }_F\mathrm{.}$ The quantity ${\delta }_F$ must come from an independent analysis of the selected fine method and its hypotheses; this corollary does not prove a local defect, stability, or continuous-time error estimate.

Let $A_t{u}_{\ast }=b$ be the fine-grid system from The all-at-once bidiagonal time operator and C/F points. By Eliminating F-points gives the exact coarse time operator, $A_t$ is invertible. Let $E$ be the exact error matrix for one fixed two-level cycle in A declared two-level MGRIT coarse-correction cycle. Choose a real-valued norm $\mathrm{\parallel }\cdot \mathrm{\parallel }$ on $({\mathbb{R}}^d{)}^N$ and define its induced operator norm by $\mathrm{\parallel }T\mathrm{\parallel }={\sup }_{v\mathrm{\ne }0}\mathrm{\parallel }Tv\mathrm{\parallel }\mathrm{/}\mathrm{\parallel }v\mathrm{\parallel }$. Assume $\mathrm{\parallel }{A}_t\mathrm{\parallel }$ and $\mathrm{\parallel }{A}_t^{-1}\mathrm{\parallel }$ are finite for this norm. If a direct calculation or other proof establishes $\mathrm{\parallel }E\mathrm{\parallel }\le q<1$, then after $r\ge 0$ cycles the error satisfies $\mathrm{\parallel }{e}^{(r)}\mathrm{\parallel }\le q^r\mathrm{\parallel }{e}^{(0)}\mathrm{\parallel }$, with the convention $q^0=1$. The residual $s^{(r)}=b-A_t{u}^{(r)}=A_t{e}^{(r)}$ obeys $\mathrm{\parallel }{s}^{(r)}\mathrm{\parallel }\le \mathrm{\parallel }{A}_t\mathrm{\parallel }{q}^r\mathrm{\parallel }{e}^{(0)}\mathrm{\parallel }$, and for every error/residual pair, $\mathrm{\parallel }s\mathrm{\parallel }\le \mathrm{\parallel }{A}_t\mathrm{\parallel }\mathrm{\parallel }e\mathrm{\parallel },\mathrm{\parallel }e\mathrm{\parallel }\le \mathrm{\parallel }{A}_t^{-1}\mathrm{\parallel }\mathrm{\parallel }s\mathrm{\parallel }\mathrm{.}$

The contraction hypothesis is a property to prove for the declared operators, norm, and cycle. The MGRIT name alone supplies no such bound, and this theorem makes no multilevel convergence claim.

Input: levels $\mathrm{\ell }=0,\dots ,L$ with $L\ge 1$; fine-grid systems $A_{\mathrm{\ell }}{u}_{\mathrm{\ell }}=b_{\mathrm{\ell }}$ of the form in The all-at-once bidiagonal time operator and C/F points; coarsening factors $m_{\mathrm{\ell }}\ge 2$ dividing $N_{\mathrm{\ell }}$ with $N_{\mathrm{\ell }+1}=N_{\mathrm{\ell }}\mathrm{/}{m}_{\mathrm{\ell }}$; transfers $P_{\mathrm{\ell }},R_{\mathrm{\ell }}$ from the F/C construction in A declared two-level MGRIT coarse-correction cycle; and pre/post-relaxations selected from its F- and FCF-relaxations. At each level $\mathrm{\ell }<L$, form the practical coarse matrix $A_{\mathrm{\ell }+1}$ with identity diagonal blocks and subdiagonal blocks $-{\mathrm{\Psi }}_{\mathrm{\ell },j}$ as in A declared two-level MGRIT coarse-correction cycle. Each noncoarsest level has a positive integer recursive visit count ${\nu }_{\mathrm{\ell }}$. Also supply an initial fine-level iterate, a chosen norm on the fine-level residual space as in A norm on a real vector space, the induced metric, and the dictionary with the metric axioms, outer cycle budget $J_{\mathrm{o}\mathrm{u}\mathrm{t}}\ge 0$, and residual tolerance $\epsilon \ge 0$. The hierarchy must provide a nonsingular coarse system at every level and an exact solve on level $L$. V-cycles use ${\nu }_{\mathrm{\ell }}=1$ and W-cycles use ${\nu }_{\mathrm{\ell }}=2$. This algorithm gives no existence or convergence claim for a hierarchy that fails these input conditions.

For a recursive call at level $\mathrm{\ell }$, perform the following operations on an initial guess $u_{\mathrm{\ell }}$:

1. If $\mathrm{\ell }=L$, solve $A_L{u}_L=b_L$ exactly by forward substitution and return.
2. Apply the selected pre-relaxation to $A_{\mathrm{\ell }}{u}_{\mathrm{\ell }}=b_{\mathrm{\ell }}$; compute $r_{\mathrm{\ell }}=b_{\mathrm{\ell }}-A_{\mathrm{\ell }}{u}_{\mathrm{\ell }}$ and restrict it to $r_{\mathrm{\ell }+1}=R_{\mathrm{\ell }}{r}_{\mathrm{\ell }}$.
3. Set the coarse correction $z_{\mathrm{\ell }+1}=0$. Repeat ${\nu }_{\mathrm{\ell }}$ times: form ${\rho }_{\mathrm{\ell }+1}=r_{\mathrm{\ell }+1}-A_{\mathrm{\ell }+1}{z}_{\mathrm{\ell }+1}$; recursively apply the level $\mathrm{\ell }+1$ cycle to $A_{\mathrm{\ell }+1}{\delta }_{\mathrm{\ell }+1}={\rho }_{\mathrm{\ell }+1}$ from zero initial correction; then set $z_{\mathrm{\ell }+1}\leftarrow z_{\mathrm{\ell }+1}+{\delta }_{\mathrm{\ell }+1}$.
4. Correct $u_{\mathrm{\ell }}\leftarrow u_{\mathrm{\ell }}+P_{\mathrm{\ell }}{z}_{\mathrm{\ell }+1}$ and apply the selected post-relaxation.

Return the updated fine-level vector when the call completes. At level $0$, check the residual before the first outer cycle and after every completed cycle; return status converged only when the residual tolerance is met. After $J_{\mathrm{o}\mathrm{u}\mathrm{t}}$ cycles without a verified residual certificate, return the last iterate with status budget-exhausted. Inexact level solves contribute explicit update defects; no such defect is hidden in the exact-arithmetic cycle.

No two-grid contraction is transferred to this recursive cycle; convergence requires a bound for its actual full recursive error operator.

Suppose initialization and all $K\ge 0$ sweeps of Finite-budget Parareal correction sweeps complete successfully. They make $KN$ 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 ${\tau }_{\mathrm{s}\mathrm{y}\mathrm{n}\mathrm{c}}\ge 0$ per sweep, their modeled work and span are respectively $W=KN{c}_F+(K+1)N{c}_G+K{\tau }_{\mathrm{s}\mathrm{y}\mathrm{n}\mathrm{c}},S=N{c}_G+K(\lceil N\mathrm{/}P\rceil c_F+N{c}_G+{\tau }_{\mathrm{s}\mathrm{y}\mathrm{n}\mathrm{c}})\mathrm{.}$ This model excludes vector arithmetic, storage, certificate verification and any overhead other than the declared synchronization cost. It gives no measured speedup guarantee.

For the literal operations of A declared two-level MGRIT coarse-correction cycle, put $N_f=N$ and $N_c=N\mathrm{/}m$. One F-relaxation uses $N_f-N_c-1$ fine-propagator calls; one C-relaxation uses $N_c$; and one FCF-relaxation uses $2(N_f-N_c-1)+N_c$. The specified coarse forward substitution uses $N_c$ practical coarse-propagator applications, including the evaluation at $z_0=0$. These counts concern completed operations without eliminating calls at zero inputs.

In an additive accounting model with nonnegative call costs $c_{\mathrm{\Phi }},c_{\mathrm{\Psi }}$, the modeled work is $n_{\mathrm{\Phi }}{c}_{\mathrm{\Phi }}+n_{\mathrm{\Psi }}{c}_{\mathrm{\Psi }}+\kappa$, where $n_{\mathrm{\Phi }},n_{\mathrm{\Psi }}$ count all executed calls and $\kappa$ accounts for all remaining work. Residuals, restriction, interpolation and stopping checks must contribute their actual calls and overhead; cached values incur no new call. A parallel schedule must respect the serial order within each F-interval and in the coarse solve, and its communication and synchronization. No measured speedup is asserted.

For one top-level call of Recursive multilevel MGRIT cycles on a finite admissible hierarchy with terminating primitive operations, the recursion terminates. Its visit counts satisfy $v_0=1$ and $v_{\mathrm{\ell }+1}={\nu }_{\mathrm{\ell }}{v}_{\mathrm{\ell }}$ for $0\le \mathrm{\ell }<L$.

Suppose every visit to noncoarsest level $\mathrm{\ell }$ has the same local call counts $n_{\mathrm{\Phi },\mathrm{\ell }},n_{\mathrm{\Psi },\mathrm{\ell }}$, excluding its recursive children. In an additive accounting model with nonnegative call costs $c_{\mathrm{\Phi },\mathrm{\ell }},c_{\mathrm{\Psi },\mathrm{\ell }}$, remaining local work ${\kappa }_{\mathrm{\ell }}$, and work $W_L$ per coarsest solve, its modeled work is $W={\sum }_{\mathrm{\ell }=0}^{L-1}{v}_{\mathrm{\ell }}(n_{\mathrm{\Phi },\mathrm{\ell }}{c}_{\mathrm{\Phi },\mathrm{\ell }}+n_{\mathrm{\Psi },\mathrm{\ell }}{c}_{\mathrm{\Psi },\mathrm{\ell }}+{\kappa }_{\mathrm{\ell }})+v_L{W}_L\mathrm{.}$ Each local F-, C- or FCF-relaxation has the literal fine-call counts $N_{\mathrm{\ell }}-N_{\mathrm{\ell }+1}-1$, $N_{\mathrm{\ell }+1}$ or $2(N_{\mathrm{\ell }}-N_{\mathrm{\ell }+1}-1)+N_{\mathrm{\ell }+1}$ respectively. Residual formation, repeated coarse residuals, restriction, interpolation and correction contribute all their actual calls and overhead; caching incurs no new call. If counts or costs vary by visit, replace each product by the sum of the corresponding visit charges. Outer stopping checks have additional costs.

Parallel execution must respect the order within each F-interval, between the successive recursive visits that update the same correction, and within each exact coarse forward solve, including communication and synchronization. The accounting model implies no measured speedup or multilevel contraction.