Finite-budget nonlinear FAS two-grid cycle

Let $U_h\subseteq {\mathbb{R}}^{n_h}$ and $U_H\subseteq {\mathbb{R}}^{n_H}$ be open, with $n_h,n_H\ge 1$. Let $F_h:U_h\to {\mathbb{R}}^{n_h}$ and $F_H:U_H\to {\mathbb{R}}^{n_H}$ be residual maps, and let $f_h\in {\mathbb{R}}^{n_h}$. The equation on the fine level is $F_h(u)=f_h$. Choose linear maps $I:{\mathbb{R}}^{n_h}\to {\mathbb{R}}^{n_H}$ (iterate restriction), $R:{\mathbb{R}}^{n_h}\to {\mathbb{R}}^{n_H}$ (residual restriction), and $P:{\mathbb{R}}^{n_H}\to {\mathbb{R}}^{n_h}$ (prolongation). No equality among $I$, $R$, and $P$ is imposed by this definition. Choose positive diagonal matrices $D^{\mathrm{p}\mathrm{r}\mathrm{e}}$ and $D^{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}$, damping factors $0<{\omega }_{\mathrm{p}\mathrm{r}\mathrm{e}},{\omega }_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}\le 1$, finite sweep counts ${\nu }_{\mathrm{p}\mathrm{r}\mathrm{e}},{\nu }_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}\in {\mathbb{N}}_0$, a finite positive coarse-solver operation budget $B_H$, and a positive integer $\gamma$.

A coarse-solver call with target $g\in {\mathbb{R}}^{n_H}$ and initial value $z\in U_H$ must return within $B_H$ declared operations either an exact selected root $(v,\mathtt{\text{exact-root}},0)$ with $F_H(v)=g$, an inexact value $(v,\mathtt{\text{inexact-root}},\eta )$ with the explicitly computed residual $\eta =\mathrm{\parallel }{F}_H(v)-g{\mathrm{\parallel }}_2>0$, or one of $\mathtt{\text{branch-failure}}$, $\mathtt{\text{domain-failure}}$, and $\mathtt{\text{budget-exhausted}}$. The solver contract requires it to return the initial value unchanged as exact-root when $F_H(z)=g$ and $z$ is the selected root. A direct formula, an exact local branch, or a finite iterative solver may be supplied; the definition makes no claim that any solver finds a root from an arbitrary initial value.

For a starting fine iterate $u\in U_h$, do the following in exact real arithmetic.

1. Perform ${\nu }_{\mathrm{p}\mathrm{r}\mathrm{e}}$ nonlinear damped-Jacobi sweeps. In each sweep, form the trial value $\tilde{u}:=u-{\omega }_{\mathrm{p}\mathrm{r}\mathrm{e}}(D^{\mathrm{p}\mathrm{r}\mathrm{e}}{)}^{-1}(F_h(u)-f_h)\mathrm{.}$ If $\tilde{u}\mathrm{\notin }{U}_h$, return the current valid fine iterate $u$ with status domain-failure; otherwise set $u:=\tilde{u}$.

2. Set $u_H=Iu$. If $u_H\mathrm{\notin }{U}_H$, return the last valid fine iterate with status domain-failure. Otherwise set $r_h=f_h-F_h(u)$ and $g_H=F_H(u_H)+R{r}_h=R{f}_h+\tau (u),\tau (u):=F_H(Iu)-R{F}_h(u)\mathrm{.}$

3. Set $z=u_H$ and initialize a finite diagnostic list $\mathrm{\Delta }=()$. For $t=1,\dots ,\gamma$, call the declared coarse solver on $(g_H,z,B_H)$. On branch-failure, domain-failure, or budget-exhausted, return the last valid fine iterate with that status and the diagnostics accumulated so far. On exact-root or inexact-root, append the returned status and residual to $\mathrm{\Delta }$, replace $z$ by the returned value, and append any nested diagnostics returned by the coarse call. Reusing $g_H$ while starting at the current $z$ makes repeated coarse calls a bounded V/W-style cycle.

4. Form the trial correction $\tilde{u}:=u+P(z-Iu)\mathrm{.}$ If $\tilde{u}\mathrm{\notin }{U}_h$, return the current valid fine iterate $u$ with status domain-failure and $\mathrm{\Delta }$; otherwise set $u:=\tilde{u}$.

5. Perform ${\nu }_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}$ nonlinear damped-Jacobi sweeps. In each sweep, form the trial value $\tilde{u}:=u-{\omega }_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}(D^{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}{)}^{-1}(F_h(u)-f_h)\mathrm{.}$ If $\tilde{u}\mathrm{\notin }{U}_h$, return the current valid fine iterate $u$ with status domain-failure and $\mathrm{\Delta }$; otherwise set $u:=\tilde{u}$. Compute the final fine residual ${\eta }_h:=\mathrm{\parallel }{F}_h(u)-f_h{\mathrm{\parallel }}_2$. Return the resulting iterate with status exact-root and residual $0$ if ${\eta }_h=0$, and with status inexact-root and residual ${\eta }_h$ if ${\eta }_h>0$, together with $\mathrm{\Delta }$. Thus the status used when this procedure is called recursively always certifies the residual for its own level equation; zero residuals reported by inner coarse calls do not by themselves certify that the returned fine iterate is a root.

Every loop count and solver budget is finite. V and W refer to the cases $\gamma =1$ and $\gamma =2$. A multi-level cycle uses this two-grid procedure at each level, with the next-level cycle supplied as the coarse solver and a finite level cap. Fixed-point consistency, linear reduction, local convergence, and work bounds are separate claims.