Multigrid methods and complexity

Let $g$ equal the slope of $v$ on the interior of each partition interval, with arbitrary values at the finitely many breakpoints. Both $v$ and $g$ are bounded, hence square integrable on $(0,1)$. Integration by parts on each partition interval gives ${\int }_0^{1}v{\phi }^{\mathrm{\prime }}=-{\int }_0^{1}g\phi$ for every $\phi \in C_c^{\mathrm{\infty }}(0,1)$: the interior endpoint terms cancel because $v$ is continuous, and the outer endpoint terms vanish because $\phi$ is compactly supported. Thus [F2] identifies $g$ as the weak derivative, and [F1] gives $v\in W^{1,2}(0,1)$.

Put $L={\max }_i\mathrm{\mid }(v{\mathrm{\mid }}_{[x_{i-1},x_i]}{)}^{\mathrm{\prime }}\mathrm{\mid }$. For $0<\delta <1\mathrm{/}4$, let ${\chi }_{\delta }$ be zero on $[0,\delta ]\cup [1-\delta ,1]$, linear from zero to one on $[\delta ,2\delta ]$, equal to one on $[2\delta ,1-2\delta ]$, and linear from one to zero on $[1-2\delta ,1-\delta ]$. Then $v_{\delta }={\chi }_{\delta }v$ is continuous and piecewise quadratic, with compact support in $[\delta ,1-\delta ]$. Its piecewise derivative is bounded; integration by parts on its finitely many pieces cancels interior boundary terms by continuity, as in step 1.1, so $v_{\delta }\in W^{1,2}(0,1)$. Since $\mathrm{\mid }v(x)\mathrm{\mid }\le L\min (x,1-x)$, its difference from $v$ is supported on strips of total length at most $4\delta$; there $\mathrm{\mid }v\mathrm{\mid }\le 2L\delta$, $\mathrm{\mid }{v}^{\mathrm{\prime }}\mathrm{\mid }\le L$, and $\mathrm{\mid }{\chi }_{\delta }^{\mathrm{\prime }}\mathrm{\mid }\le 1\mathrm{/}\delta$. The product rule therefore gives $\mathrm{\parallel }v-v_{\delta }{\mathrm{\parallel }}_{L^2}^2\le 16L^2{\delta }^3$ and $\mathrm{\parallel }(v-v_{\delta }{)}^{\mathrm{\prime }}{\mathrm{\parallel }}_{L^2}^2\le 36L^2\delta$. The $W^{1,2}$ formula in [F1] then gives $v_{\delta }\to v$ in $W^{1,2}(0,1)$ as $\delta \to 0^{+}$.

Extend $v_{\delta }$ by zero to $V_{\delta }\in W^{1,2}(\mathbb{R})$ using [F5]. Choose the [F6] bump with $r=1\mathrm{/}2$ and $R=1$. Its integral $c$ is finite because it is bounded and supported in $(-1,1)$, and $c\ge 1$ because it equals $1$ on an interval of length $1$. Normalize it by $c$ and take its mollifier family from [F7]. The convolution $V_{\delta }\ast {\rho }_{\epsilon }$ is smooth by [F10]. Differentiating under the integral and integrating by parts on the finitely many polynomial pieces of $V_{\delta }$ gives $(V_{\delta }\ast {\rho }_{\epsilon }{)}^{\mathrm{\prime }}=V_{\delta }^{\mathrm{\prime }}\ast {\rho }_{\epsilon }$: interior boundary terms cancel by continuity and outer terms vanish by compact support. By [F8]–[F9], the function and its derivative converge in $L^2(\mathbb{R})$ to $V_{\delta }$ and $V_{\delta }^{\mathrm{\prime }}$ as $\epsilon \to 0^{+}$. The normalized bump has support in $[-1,1]$, so $0<\epsilon <\delta$ places the convolution support inside $(0,1)$ and it belongs to $C_c^{\mathrm{\infty }}(0,1)$.

Given $\eta >0$, choose $\delta$ so that step 2.1 gives $\mathrm{\parallel }v-v_{\delta }{\mathrm{\parallel }}_{W^{1,2}}<\eta \mathrm{/}2$, and then choose sufficiently small $\epsilon$ in step 3.1 so that $\mathrm{\parallel }{v}_{\delta }-(V_{\delta }\ast {\rho }_{\epsilon }){\mathrm{\mid }}_{(0,1)}{\mathrm{\parallel }}_{W^{1,2}}<\eta \mathrm{/}2$. The triangle inequality [F4] gives a $C_c^{\mathrm{\infty }}(0,1)$ approximation to $v$ within $\eta$. Since $\eta$ was arbitrary, [F3] yields $v\in H_0^1(0,1)$.

For every nonzero $q\in {\mathbb{R}}^m$, full column rank gives $Pq\mathrm{\ne }0$, so $q^{\mathsf{T}}{A}_{H}q=(Pq{)}^{\mathsf{T}}{A}_h(Pq)>0$. Also $A_H^{\mathsf{T}}=P^{\mathsf{T}}{A}_h^{\mathsf{T}}P=A_H$ by [F4]. Thus $A_H$ is symmetric positive definite and [F2] makes it invertible; [F1] therefore defines $C$.

From $P^{\mathsf{T}}{A}_{h}P=A_H$, direct multiplication gives $CP=P-P{A}_H^{-1}{A}_H=0$ and $P^{\mathsf{T}}{A}_{h}C=P^{\mathsf{T}}{A}_h-A_H{A}_H^{-1}{P}^{\mathsf{T}}{A}_h=0$. Moreover, $C^2=I_n-2P{A}_H^{-1}{P}^{\mathsf{T}}{A}_h+P{A}_H^{-1}(P^{\mathsf{T}}{A}_{h}P)A_H^{-1}{P}^{\mathsf{T}}{A}_h=C\mathrm{.}$

Transposing $A_H{A}_H^{-1}=I=A_H^{-1}{A}_H$ and using [F4] shows that $(A_H^{-1}{)}^{\mathsf{T}}$ is an inverse of $A_H^{\mathsf{T}}=A_H$. If $B$ and $D$ are two-sided inverses of $A_H$, then $B=B(A_{H}D)=(B{A}_H)D=D$, so the inverse is unique and $(A_H^{-1}{)}^{\mathsf{T}}=A_H^{-1}$. Thus [F4] yields $C^{\mathsf{T}}{A}_h=A_h-A_{h}P{A}_H^{-1}{P}^{\mathsf{T}}{A}_h=A_{h}C$, so $C$ is self-adjoint in [F3]. Also $P^{\mathsf{T}}{A}_{h}C=0$ says $\mathrm{Ran}(C)\subseteq \mathrm{Ran}(P{)}^{{\perp }_{A_h}}$. If $w$ is in that complement, then $P^{\mathsf{T}}{A}_{h}w=0$, so [F1] gives $Cw=w$; therefore every such $w$ is in $\mathrm{Ran}(C)$ and the ranges are equal.

The identities in step 2.1 and the range equality in step 3.1 prove all stated projection properties.

Extend a fine vector by $x_0=x_N=0$. Direct expansion gives $x^{\mathsf{T}}{A}_{h}x=h^{-1}{\sum }_{i=1}^N(x_i-x_{i-1}{)}^2\mathrm{.}$ This is positive for every nonzero $x$, since a zero sum forces all consecutive entries equal and the boundary entries are zero. The even rows of $P$ form the identity on coarse coordinates, so $P$ has full column rank. Thus [F2] ensures $A_H$ is invertible and $C$ is defined.

For any $x$, $(x_i-x_{i-1}{)}^2\le 2x_i^2+2x_{i-1}^2$ and the endpoints vanish, so $x^{\mathsf{T}}{A}_{h}x\le (4\mathrm{/}h)\mathrm{\parallel }x{\mathrm{\parallel }}_2^2$. By [F4], $0<\lambda \le {\lambda }_{\max }(A_h)\le 4\mathrm{/}h$ for each eigenvalue. In an orthonormal eigenbasis, $S$ has eigenvalues $1-\lambda \mathrm{/}{\lambda }_{\max }\in [0,1)$. For $\xi =\lambda \mathrm{/}{\lambda }_{\max }\in (0,1]$, the finite geometric identity $\xi {\sum }_{k=0}^{2\nu }(1-\xi {)}^k=1-(1-\xi {)}^{2\nu +1}\le 1$ applies. Each summand is at least $(1-\xi {)}^{2\nu }$, so $\xi (1-\xi {)}^{2\nu }\le 1\mathrm{/}(2\nu +1)$. Expanding $e$ in that eigenbasis yields $\mathrm{\parallel }{A}_h{S}^{\nu }e{\mathrm{\parallel }}_2^2\le \frac{{\lambda }_{\max }(A_h)}{2\nu +1}\mathrm{\parallel }e{\mathrm{\parallel }}_{A_h}^2\le \frac{4}{h(2\nu +1)}\mathrm{\parallel }e{\mathrm{\parallel }}_{A_h}^2\mathrm{.}$

Let $J$ insert a coarse vector into the even fine indices and zero the odd indices. At an odd fine row, $A_{h}Pv=0$ because $2(Pv{)}_{2j+1}=(Pv{)}_{2j}+(Pv{)}_{2j+2}$. At an even row $2j$, $(A_{h}Pv{)}_{2j}=(2h{)}^{-1}(2v_j-v_{j-1}-v_{j+1}),$ with boundary values $v_0=v_M=0$. Direct multiplication gives $A_H$ diagonal entries $1\mathrm{/}h$, adjacent entries $-1\mathrm{/}(2h)$, and all other entries zero; hence $A_{h}P=J{A}_H$ and, by [F5], $P^{\mathsf{T}}{A}_h=A_H{J}^{\mathsf{T}}$. Substitution in [F1] yields $C=I-P{J}^{\mathsf{T}}$. Therefore $y=Cw$ has zero even entries. Also $A_{h}y=A_{h}w-J{A}_H{J}^{\mathsf{T}}w$, so the odd entries of $A_{h}y$ equal those of $A_{h}w$.

For odd $i$, the two neighbours of $y_i$ are even and zero, so $(A_{h}y{)}_i=2y_i\mathrm{/}h=(A_{h}w{)}_i$. Therefore $\mathrm{\parallel }Cw{\mathrm{\parallel }}_2^2={\sum }_{i\text{ odd}}{y}_i^2=\frac{h^2}{4}{\sum }_{i\text{ odd}}(A_{h}w{)}_i^2\le \frac{h^2}{4}\mathrm{\parallel }{A}_{h}w{\mathrm{\parallel }}_2^2\mathrm{.}$ Since each odd value is adjacent to two zero even values, the energy identity in step 1.1 gives $\mathrm{\parallel }y{\mathrm{\parallel }}_{A_h}^2=(2\mathrm{/}h)\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$. Thus $\mathrm{\parallel }Cw{\mathrm{\parallel }}_{A_h}^2\le (h\mathrm{/}2)\mathrm{\parallel }{A}_{h}w{\mathrm{\parallel }}_2^2$.

Apply the approximation estimate of step 3.1 with $w=S^{\nu }e$ and then the smoothing estimate of step 1.2: $\mathrm{\parallel }C{S}^{\nu }e{\mathrm{\parallel }}_{A_h}^2\le \frac{h}{2}\mathrm{\parallel }{A}_h{S}^{\nu }e{\mathrm{\parallel }}_2^2\le \frac{2}{2\nu +1}\mathrm{\parallel }e{\mathrm{\parallel }}_{A_h}^2\mathrm{.}$ Because $\nu \ge 1$, $2\mathrm{/}(2\nu +1)\le 2\mathrm{/}3<1$, uniformly in $N$.

Put $u=Sx$. Since $C^2=C$ and $C$ is $A_h$-self-adjoint, $C(I-C)=0$ and $⟨Cu,(I-C)u{⟩}_{A_h}=⟨u,C(I-C)u{⟩}_{A_h}=0$. Thus [F1] gives $⟨Ex,x{⟩}_{A_h}=⟨CSx,Sx{⟩}_{A_h}=⟨CSx,CSx{⟩}_{A_h}=\mathrm{\parallel }CSx{\mathrm{\parallel }}_{A_h}^2\ge 0.$

For all $x,y$, the adjoint identity in [F1] and self-adjointness of $C$ in [F2] give $⟨Ex,y{⟩}_{A_h}=⟨CSx,Sy{⟩}_{A_h}=⟨Sx,CSy{⟩}_{A_h}=⟨x,Ey{⟩}_{A_h}\mathrm{.}$ Hence $E$ is self-adjoint.

By [F5], choose an $A_h$-orthonormal eigenbasis $v_1,\dots ,v_n$ for the self-adjoint map $E$, with eigenvalues ${\lambda }_j$. Step 1.1 gives ${\lambda }_j=⟨E{v}_j,v_j{⟩}_{A_h}\ge 0$; the joint hypothesis gives ${\lambda }_j=\mathrm{\parallel }CS{v}_j{\mathrm{\parallel }}_{A_h}^2\le \rho$. For $x={\sum }_j{c}_j{v}_j$, orthonormality yields $\mathrm{\parallel }Ex{\mathrm{\parallel }}_{A_h}^2={\sum }_j{\lambda }_j^2{c}_j^2\le {\rho }^2{\sum }_j{c}_j^2={\rho }^2\mathrm{\parallel }x{\mathrm{\parallel }}_{A_h}^2\mathrm{.}$ The nonzero finite-dimensional domain has an attained operator-norm maximum by [F6], so taking the maximum over unit $x$ in [F4] proves $\mathrm{\parallel }E{\mathrm{\parallel }}_{A_h}\le \rho$. Since $\rho <1$, the two-grid error map is a strict energy contraction.

At any aggregation pass the unassigned set $U$ is finite and nonempty. The selected smallest vertex $i$ belongs to the new aggregate, so at least one vertex is removed. No previously removed vertex can reappear because every neighbour is intersected with $U$. Thus the aggregates are pairwise disjoint and, when the finite loop ends at $U=\mathrm{\varnothing }$, cover all current indices. Each aggregate is nonempty. If $Pz=0$, choose any row index in aggregate $r$; its row has a single $1$ in column $r$, so that component of $Pz$ is $z_r=0$. This holds for every $r$, hence $P$ has full column rank.

By [F2] and step 1.1, $A_{\mathrm{\ell }+1}=P_{\mathrm{\ell }}^{\mathsf{T}}{A}_{\mathrm{\ell }}{P}_{\mathrm{\ell }}$ is SPD. For distinct aggregate columns $r\mathrm{\ne }s$, disjointness gives $(A_{\mathrm{\ell }+1}{)}_{rs}={\sum }_{i\in C_r}{\sum }_{j\in C_s}{a}_{ij}^{(\mathrm{\ell })}\le 0,$ since $i\mathrm{\ne }j$ in every summand and the fine matrix has nonpositive off-diagonal entries. Symmetry follows from symmetry of $A_{\mathrm{\ell }}$. Induction over successful levels proves the same matrix class at each returned level.

Each aggregation pass is finite by step 1.1. A pass is attempted only when $\mathrm{\ell }+1\le L$, so the number of attempts is an integer at most $\lfloor L\rfloor$. At each outer iteration, step 1 returns coarse-reached when $n_{\mathrm{\ell }}\le n_{\min }$; otherwise the cap test in [F1] returns level-cap when $\mathrm{\ell }+1>L$. If neither branch applies, a pass is performed and either $n_{\mathrm{\ell }+1}\ge n_{\mathrm{\ell }}$ returns coarsening-stalled, or the procedure advances to the next level. These ordered branches exhaust the procedure, so it terminates with exactly one listed status.

The preceding steps establish the partition, rank, matrix-class and status claims. No step asserts a contraction factor.

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 $\gamma$ of terminating calls at level $j-1$. Hence every invocation on every admissible finite hierarchy terminates.

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

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

If $\gamma =q$, the sum in step 2.1 is $L$, and ${\gamma }^{L}T(1)=NT(1)=\mathrm{\Theta }(N)$. Since $L={\log }_{q}N$, this gives $T(N)=\mathrm{\Theta }(N\log N)$.

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

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.

By [F1], the pre-smoother $S^{\nu }$ satisfies the joint estimate with $\rho =2\mathrm{/}(2\nu +1)$. For $\nu \ge 1$, $0<\rho \le 2\mathrm{/}3<1$.

Apply [F3] to the symmetric error map [F2] with this value of $\rho$. It follows that $\mathrm{\parallel }E{\mathrm{\parallel }}_{A_h}\le 2\mathrm{/}(2\nu +1)\le 2\mathrm{/}3$, independently of $N$.