Nonlinear full-approximation multigrid

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.

Let $X_0,X_1,X_2,X_3$ be finite-dimensional real Euclidean spaces and let $U_i\subseteq X_i$ be open for $i=0,1,2$. Suppose $S:U_0\to U_1$, $C:U_1\to U_2$, and $T:U_2\to X_3$ are $C^2$, meaning that each is totally differentiable with continuous derivative and that its derivative map is itself totally differentiable. Write $\mathcal{L}(X,Y)$ for the finite-dimensional space of linear maps $X\to Y$ with the induced Euclidean operator norm. Put $E=T\circ C\circ S$. For a $C^2$ map $f$, define $D^{2}f(x)[h,k]:=(D(Df)(x)h)k$. At $x\in U_0$, set $y=S(x)$ and $z=C(y)$. Then for all $h,k\in X_0$, $D^{2}E(x)[h,k]=D^{2}T(z)[DC(y)DS(x)h,DC(y)DS(x)k]+DT(z)(D^{2}C(y)[DS(x)h,DS(x)k]+DC(y)D^{2}S(x)[h,k])\mathrm{.}$

Fix a finite hierarchy of levels $j=0,1,\dots ,J$ with $J\ge 1$. At level $j$, let $F_j:U_j\to {\mathbb{R}}^{n_j}$ be defined on an open $U_j\subseteq {\mathbb{R}}^{n_j}$, let $f_j\in {\mathbb{R}}^{n_j}$, and provide the linear transfers $I_j$, $R_j$, and $P_j$ with the dimensions in Finite-budget nonlinear FAS two-grid cycle. For each $j>0$, provide the two diagonal smoother matrices, damping factors, and finite pre/post sweep counts from that algorithm. Choose a finite base solver at level $0$ with a declared total operation budget $B_0$ and statuses exact-root, inexact-root, branch-failure, domain-failure, and budget-exhausted. Its exact-root and inexact-root statuses must report $\mathrm{\parallel }{F}_0(v)-f_0{\mathrm{\parallel }}_2$ as $0$ and a positive number, respectively. At each noncoarsest level choose ${\gamma }_j\in \{1,2\}$, representing V and W recursion, respectively. For every $j>0$, the recursive level-$(j-1)$ solver call in the two-grid procedure is metered against its declared finite coarse-call budget; if it exceeds that budget, it returns budget-exhausted with its last valid iterate.

The base-solver contract also requires it to return its initial value unchanged with status exact-root whenever that value already satisfies $F_0(z)=f_0$.

Define $\mathrm{Cycle}(0,u,f_0)$ to call the base solver. For $j>0$, provide the level-$(j-1)$ cycle as the coarse-solver interface to Finite-budget nonlinear FAS two-grid cycle: its reported residual is measured as $\mathrm{\parallel }{F}_{j-1}(v)-g{\mathrm{\parallel }}_2$, where $v$ is the returned value, with exact-root only at residual zero and inexact-root only at positive residual. The two-grid procedure makes ${\gamma }_j$ calls with the same coarse right side $g$ and the current coarse iterate $z$. Return the two-grid output, its status, its level residual, and the finite diagnostic list of coarse-call residuals. Any failure status propagates immediately with the last valid fine-level iterate. Each recursive call lowers $j$, and all within-level loops have the finite budgets required by Finite-budget nonlinear FAS two-grid cycle.

The V-cycle is the choice ${\gamma }_j=1$ on each noncoarsest level; the W-cycle is ${\gamma }_j=2$. This definition does not assert that the returned iterate solves the nonlinear equations, that the cycles converge, or that their work is linear in the number of fine unknowns.

Consider one exact-branch two-grid cycle from Finite-budget nonlinear FAS two-grid cycle. Let $F_h:U_h\to {\mathbb{R}}^{n_h}$ and $F_H:U_H\to {\mathbb{R}}^{n_H}$ be $C^1$ on open sets, let $I,R,P$ be linear, and suppose $F_h(u_{\ast })=f_h$ and $I{u}_{\ast }\in U_H$. Assume the exact coarse solver selects the local root branch through $I{u}_{\ast }$ and $D{F}_H(I{u}_{\ast })$ is invertible. Suppose the pre/post smoothing maps are $C^1$ and fix $u_{\ast }$. The selected coarse root $v(u)$ is locally $C^1$, and the derivative of the actual FAS cycle $E$ at $u_{\ast }$ is $DE(u_{\ast })=D{S}^{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}(u_{\ast })[I_{n_h}-PD{F}_H(I{u}_{\ast }{)}^{-1}RD{F}_h(u_{\ast })]D{S}^{\mathrm{p}\mathrm{r}\mathrm{e}}(u_{\ast })\mathrm{.}$

No identity between $R$ and $I$, or between the coarse operator and a rediscretized fine operator, is assumed in this derivative formula.

Consider an invocation of Finite-budget recursive nonlinear FAS V/W cycle on levels $0,\dots ,J$, where the base solver uses at most $B_0<\mathrm{\infty }$ counted operations, every nonlinear smoother update and residual evaluation returns in finite work, and every transfer and correction is a finite-dimensional map evaluation. The invocation terminates with one of its declared statuses. If $W_j$ is the maximum counted work of a level-$j$ invocation, then $W_0\le B_0,W_j\le C_j+{\gamma }_j{W}_{j-1}(1\le j\le J),$ where $C_j$ is the finite work of that level's pre-smoothing, residual and transfer evaluations, correction, post-smoothing, and status/diagnostic bookkeeping. This recurrence counts the actual nonlinear smoother, coarse-solve, and returned-diagnostic work; it implies no blanket $O(n_J)$ estimate.

For a level-$j$ invocation of Finite-budget recursive nonlinear FAS V/W cycle, let $u^{\ast }$ satisfy $F_j(u^{\ast })=f_j$. Suppose each selected pre/post smoother leaves every exact root fixed, every restriction $I_j{u}^{\ast }$ lies in $U_{j-1}$ and is selected as the exact coarse root at its zero-defect target, and the base solver returns any initial exact root unchanged. Then the exact-branch FAS V/W cycle leaves $u^{\ast }$ fixed. This holds for arbitrary admissible transfer maps $I_j,R_j,P_j$; no identity such as $R_j=I_j$ or $I_j{P}_j=I$ is needed.

Let $E:U\to {\mathbb{R}}^n$ be the actual exact-branch error map of one fixed FAS two-grid or recursive V/W cycle, with $U\subseteq {\mathbb{R}}^n$ open. Let $u_{\ast }\in U$ be a fine root for which the selected smoothers and coarse branches fix $u_{\ast }$, so $E(u_{\ast })=u_{\ast }$. Assume $E$ is $C^1$ on a neighborhood of the closed Euclidean ball $K={\bar{B}}_2(u_{\ast },r)\subset U$. Put $q=\mathrm{\parallel }DE(u_{\ast }){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$, where for a linear map $T$ the induced Euclidean operator norm is $\mathrm{\parallel }T{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}:={\sup }_{\mathrm{\parallel }v{\mathrm{\parallel }}_2=1}\mathrm{\parallel }Tv{\mathrm{\parallel }}_2$. Suppose $q<1$ and $\mathrm{\parallel }DE(x)-DE(y){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le L\mathrm{\parallel }x-y{\mathrm{\parallel }}_2(x,y\in K)$ for some $L\ge 0$. If $q+Lr\mathrm{/}2<1$, then $E(K)\subseteq K$ and every iteration $u_{k+1}=E(u_k)$ starting in $K$ satisfies $\mathrm{\parallel }{u}_k-u_{\ast }{\mathrm{\parallel }}_2\le (q+Lr\mathrm{/}2{)}^k\mathrm{\parallel }{u}_0-u_{\ast }{\mathrm{\parallel }}_2\mathrm{.}$ This is a local result for the derivative of the actual cycle; it supplies no global-start or mesh-independent rate unless $q,L,r$ are verified uniformly.

For the two-grid exact-branch cycle, Derivative of the exact-branch FAS two-grid cycle gives the derivative to be checked. For a recursive V/W cycle, the bound must be checked for the complete composed cycle. The one-sided estimate toward $u_{\ast }$ does not assert a Banach contraction bound between every pair of points in $K$.

For the linear Galerkin V/W-cycle procedure of Finite recursive Galerkin V- and W-cycle for an SPD hierarchy, on any level $j$ and for all $x,a,b\in {\mathbb{R}}^{n_j}$, $\mathrm{Cycle}(j,x+a,b+A_{j}a)=a+\mathrm{Cycle}(j,x,b)\mathrm{.}$ The identity is in exact arithmetic and uses the same hierarchy, smoothing matrices, sweep counts, and cycle count on both sides.

Let $A_j\in {\mathbb{R}}^{n_j\times n_j}$, $0\le j\le J$, be a finite SPD Galerkin hierarchy with full-column-rank prolongations $P_j$ and $A_{j-1}=P_j^{\mathsf{T}}{A}_j{P}_j$. At each level set $F_j(u)=A_{j}u$, $R_j=P_j^{\mathsf{T}}$, and use the exact Galerkin coarse operator $F_{j-1}(v)=A_{j-1}v$, matching residual-correction pre/post smoothers, and the same finite sweep and V/W cycle counts in Finite-budget recursive nonlinear FAS V/W cycle and Finite recursive Galerkin V- and W-cycle for an SPD hierarchy. The exact-branch FAS V/W procedure returns exactly the same iterate as the corresponding linear Galerkin correction V/W-cycle. The iterate restriction $I_j$ may be any linear map of the stated dimensions.

Consider one two-grid FAS cycle with fixed pre-smoothing result, exact selected coarse root $v(u)$, prolongation $P$, and a post-smoother that is $L_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}$-Lipschitz on the relevant corrected states. Suppose a coarse solver returns $\widehat{v}$ with residual $\eta =\mathrm{\parallel }{F}_H(\widehat{v})-g_H(u){\mathrm{\parallel }}_2$ and a separately verified residual-to-solution estimate $\mathrm{\parallel }\widehat{v}-v(u){\mathrm{\parallel }}_2\le M_H\eta \mathrm{.}$ Then the inexact-cycle output $\widehat{E}(u)$ and exact-cycle output $E(u)$ satisfy $\mathrm{\parallel }\widehat{E}(u)-E(u){\mathrm{\parallel }}_2\le L_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}\mathrm{\parallel }P{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}{M}_H\eta \mathrm{.}$ If the exact cycle satisfies the root-error estimate $\mathrm{\parallel }E(u)-u_{\ast }{\mathrm{\parallel }}_2\le \kappa \mathrm{\parallel }u-u_{\ast }{\mathrm{\parallel }}_2$ on a stated invariant region, then for every iteration input $u_k$ in that region whose exact and inexact corrected states satisfy the preceding hypotheses, $\mathrm{\parallel }{u}_{k+1}-u_{\ast }{\mathrm{\parallel }}_2\le \kappa \mathrm{\parallel }{u}_k-u_{\ast }{\mathrm{\parallel }}_2+L_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}}\mathrm{\parallel }P{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}{M}_H{\eta }_k\mathrm{.}$ Invertibility of $D{F}_H$ alone is not asserted to imply the stated residual-to-solution estimate; that bound must be proved under additional coarse-operator hypotheses.

On $\mathrm{\Omega }=(0,3)$ with homogeneous endpoint values, the $h=1$ centered finite-difference discretization of the semilinear equation $-u^{\mathrm{\prime }\mathrm{\prime }}+u^3=0$ has fine residual $F(u)=Au+(u_1^3,u_2^3),A=\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)\mathrm{.}$ Use $P=(1,1{)}^{\mathsf{T}}$, $Iu=(u_1+u_2)\mathrm{/}2$, $R=P^{\mathsf{T}}$, the Galerkin coarse residual $F_H(v)=P^{\mathsf{T}}F(Pv)$, one pre- and one post-sweep $S(u)=u-\frac{1}{4}F(u)$, and the exact selected coarse root. The unique fine root is $u_{\ast }=0$. The actual exact-branch FAS two-grid map is a contraction toward $u_{\ast }$ on ${\bar{B}}_2(0,1\mathrm{/}100)$ with error factor at most $27\mathrm{/}400$.

Given: The mesh nodes $0,1,2,3$, endpoint values $u_0=u_3=0$, the fine operator and transfers in the Statement, and exact coarse root selection.