Overlapping Schwarz and stable subspace decompositions — Examples

Put $r=H\mathrm{/}\delta$. Substituting into [F1] gives $C_0\le C_{\mathrm{F}\mathrm{E}}(1+r^2)$.

To exhibit admissible radii with $\delta \mathrm{/}H\to 0$, fix $M,d$, put $a=1\mathrm{/}M$, choose $q_0=\lceil \sqrt{d}\rceil$, and take $\delta =q_{0}a\mathrm{/}n$ as $n\to \mathrm{\infty }$ with $n\ge q_0$. Then $h=\sqrt{d}a\mathrm{/}n\le \delta \le a$, and $r=H\mathrm{/}\delta =\sqrt{d}n\mathrm{/}{q}_0\to \mathrm{\infty }$. The right side of the one-sided upper-bound formula grows; it supplies no lower estimate on the actual stable constant or condition number.

Direct expansion gives $x^{\mathsf{T}}{A}_{N}x=h^{-1}{\sum }_{j=1}^N(x_j-x_{j-1}{)}^2$ with $x_0=x_N=0$. It is positive for every nonzero vector because vanishing of all successive differences and $x_0=0$ forces every $x_j=0$. For the point-patch injection $R_i=e_i$, the local matrix is $A_i=e_i^{\mathsf{T}}{A}_N{e}_i=2\mathrm{/}h$. Thus [F1] gives $B_N={\sum }_i{e}_i(h\mathrm{/}2)e_i^{\mathsf{T}}=(h\mathrm{/}2)I$. Each corresponding nodal hat is supported on two adjacent mesh intervals, so neighboring local supports overlap and at most three closed supports meet at a point.

For $k=1,\dots ,N-1$, set $v_j^{(k)}=\sin (jk\pi \mathrm{/}N)$ for $j=0,\dots ,N$. The endpoints vanish. With $\theta =k\pi \mathrm{/}N$, the identity $v_{j-1}^{(k)}+v_{j+1}^{(k)}=2\cos (\theta )v_j^{(k)}$ gives $A_N{v}^{(k)}=\frac{2}{h}(1-\cos \theta )v^{(k)}\mathrm{.}$ These eigenvalues are distinct because cosine is strictly decreasing on $(0,\pi )$. Since $A_N$ is symmetric, eigenvectors for distinct eigenvalues are orthogonal: for $k\mathrm{\ne }l$, $({\lambda }_k-{\lambda }_l)(v^{(k)}{)}^{\mathsf{T}}{v}^{(l)}=(A_N{v}^{(k)}{)}^{\mathsf{T}}{v}^{(l)}-(v^{(k)}{)}^{\mathsf{T}}{A}_N{v}^{(l)}=0$. The vectors are nonzero, so the $N-1$ orthogonal vectors form a basis of ${\mathbb{R}}^{N-1}$. Multiplication by $B_N=(h\mathrm{/}2)I$ gives eigenvalues $1-\cos (k\pi \mathrm{/}N)$ for $B_N{A}_N$.

The smallest and largest values occur at $k=1$ and $k=N-1$, respectively. Therefore ${\kappa }_A(B_N{A}_N)=\frac{1-\cos ((N-1)\pi \mathrm{/}N)}{1-\cos (\pi \mathrm{/}N)}=\frac{1+\cos (\pi \mathrm{/}N)}{1-\cos (\pi \mathrm{/}N)}\mathrm{.}$ As $N\to \mathrm{\infty }$ the numerator tends to $2$ and the positive denominator tends to $0$, so the condition numbers diverge.

The grounded two-node graph with unit conductance from each node to ground and conductance $\alpha$ between the nodes has matrix $A_{\alpha }=I_2+\alpha \left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)\mathrm{.}$ For $x=(x_1,x_2)$, $x^{\mathsf{T}}{A}_{\alpha }x=x_1^2+x_2^2+\alpha (x_1-x_2{)}^2$, so $A_{\alpha }$ is SPD. The coarse and local injections are $R_0=e_1$ and $R_1=e_2$, hence $A_0=A_1=1+\alpha$. The additive preconditioner from [F1] is therefore $B_{\alpha }=(1+\alpha {)}^{-1}{I}_2$. There is one local subspace, so its pairwise overlap matrix is the fixed $1\times 1$ matrix $[1]$, independent of $\alpha$.

The vectors $(1,1)$ and $(1,-1)$ are eigenvectors of $A_{\alpha }$ with eigenvalues $1$ and $1+2\alpha$. Thus $B_{\alpha }{A}_{\alpha }$ has eigenvalues $(1+\alpha {)}^{-1}$ and $(1+2\alpha )\mathrm{/}(1+\alpha )$, so ${\kappa }_A(B_{\alpha }{A}_{\alpha })=1+2\alpha \to \mathrm{\infty }$. The low-energy channel vector $(1,1)$ is not in the one-node coarse space $V_0$, and the growing condition number disproves the claim.

Given a fine vector $u$, let $u_H$ be its coarse nodal interpolant: $(u_H{)}_{2k}=u_{2k}$ and $(u_H{)}_{2k-1}=(u_{2k-2}+u_{2k})\mathrm{/}2$. Define ${\eta }_k=u_{2k-1}-(u_{2k-2}+u_{2k})\mathrm{/}2$ and $u_k={\eta }_k{\varphi }_{2k-1}$. Nodal values give $u=u_H+{\sum }_{k=1}^M{u}_k$.

On each fine interval, at most one odd nodal hat has nonzero derivative. Thus only the coarse derivative and at most one local derivative can be nonzero there. The elementary inequality $(s+t{)}^2\le 2(s^2+t^2)$, which follows from $(s-t{)}^2\ge 0$, and integration give ${\parallel v_0+{\sum }_k{v}_k\parallel }_A^2\le 2(\mathrm{\parallel }{v}_0{\mathrm{\parallel }}_A^2+{\sum }_k\mathrm{\parallel }{v}_k{\mathrm{\parallel }}_A^2)\mathrm{.}$ Hence $C_1\le 2$.

On each pair of fine intervals set $a_k=u_{2k-1}-u_{2k-2}$ and $b_k=u_{2k}-u_{2k-1}$. The coarse energy on that coarse interval is $(a_k+b_k{)}^2\mathrm{/}(2h)\le (a_k^2+b_k^2)\mathrm{/}h$, exactly its fine energy contribution. Summing over $k$ gives $\mathrm{\parallel }{u}_H{\mathrm{\parallel }}_A^2\le \mathrm{\parallel }u{\mathrm{\parallel }}_A^2$.

Since ${\eta }_k=(a_k-b_k)\mathrm{/}2$ and $(a_k-b_k{)}^2\le 2(a_k^2+b_k^2)$, the local energy is $\mathrm{\parallel }{u}_k{\mathrm{\parallel }}_A^2=2{\eta }_k^2\mathrm{/}h\le (a_k^2+b_k^2)\mathrm{/}h$. Summing gives ${\sum }_k\mathrm{\parallel }{u}_k{\mathrm{\parallel }}_A^2\le \mathrm{\parallel }u{\mathrm{\parallel }}_A^2$. The decomposition in step 1.1 therefore has total energy at most $2\mathrm{\parallel }u{\mathrm{\parallel }}_A^2$, so $C_0\le 2$.

Apply [F1] to the exact Schwarz data [F2] with $C_0\le 2$ and $C_1\le 2$ to obtain ${\kappa }_A(BA)\le 4$. This finite one-dimensional split has a global coarse space; higher-dimensional overlap estimates are handled separately on the A page.

The coordinate decomposition is stable with $C_0=1$, and its synthesis bound is $C_1=1$ because $\mathrm{\parallel }{z}_1{e}_1+z_2{e}_2{\mathrm{\parallel }}_2^2=z_1^2+z_2^2$. Exact local matrices equal $1$, so [F2] gives $B=I_2$ and condition number $1$.

The inexact local inverses are $1\mathrm{/}4$ and $2$, so [F2] gives $\tilde{B}=\mathrm{diag}(1\mathrm{/}4,2)$. Its eigenvalues are $1\mathrm{/}4$ and $2$, hence ${\kappa }_A(\tilde{B}A)=8$. The choices $\alpha =1\mathrm{/}4$ and $\beta =4$ satisfy the local order bounds.

Substitution of $C_0=C_1=1$, $\alpha =1\mathrm{/}4$, and $\beta =4$ into [F1] gives the rigorous upper bound $16$, which contains the directly computed value $8$.