Parallel in time parareal and mgrit — Examples

By [F1], one fine microstep maps $x$ to $x-\frac{1}{4}x=\frac{3}{4}x$, so the two-step fine macro map is $F(x)=\frac{9}{16}x$. By [F2], the coarse backward-Euler equation is $z=x-\frac{1}{2}z$, whose unique solution is $G(x)=\frac{2}{3}x$.

The sequential fine values are $x_1=\frac{9}{16}$ and $x_2=\frac{81}{256}$, while coarse initialization gives $U_1^0=\frac{2}{3}$ and $U_2^0=\frac{4}{9}$.

The first correction has $U_1^1=F(1)=\frac{9}{16}$. Using [F3], $U_2^1=G(\frac{9}{16})+(F-G)(\frac{2}{3})=\frac{3}{8}+(\frac{9}{16}-\frac{2}{3})\frac{2}{3}=\frac{11}{36}$.

Direct subtraction gives $\mathrm{\mid }{U}_2^0-x_2\mathrm{\mid }=\mathrm{\mid }\frac{4}{9}-\frac{81}{256}\mathrm{\mid }=\frac{295}{2304}$ and $\mathrm{\mid }{U}_2^1-x_2\mathrm{\mid }=\mathrm{\mid }\frac{11}{36}-\frac{81}{256}\mathrm{\mid }=\frac{25}{2304}$. Thus the error decreases for these parameters; the calculation does not assert monotone decrease for other propagators.

The coarse initialization is $U_1^0=-x_0$ and $U_2^0=x_0$, while the sequential fine endpoint is $x_2=F^2{x}_0=x_0$. Both maps preserve the Euclidean norm because $\mathrm{\parallel }Ix{\mathrm{\parallel }}_2=\mathrm{\parallel }-Ix{\mathrm{\parallel }}_2=\mathrm{\parallel }x{\mathrm{\parallel }}_2$.

By [F1], $U_1^1=G{x}_0+(F-G)x_0=-x_0+2x_0=x_0$, and $U_2^1=G{x}_0+(F-G)(-x_0)=-x_0-2x_0=-3x_0$.

Therefore $\mathrm{\parallel }{U}_2^1-x_2{\mathrm{\parallel }}_2=\mathrm{\parallel }-4x_0{\mathrm{\parallel }}_2=4$. Since $K=N=2$, [F2] gives $U_2^2=x_2$. The error growth at the first sweep is transient and does not contradict finite-step exactness.

For $x,y\in D$, $\mathrm{\mid }G(x)-G(y)\mathrm{\mid }=\mathrm{\mid }x-y\mathrm{\mid }$. Also $(F-G)(x)-(F-G)(y)=(x-y)(x+y-1)$, and $\mathrm{\mid }x+y-1\mathrm{\mid }\le 1$ on $D$, so $F-G$ is $1$-Lipschitz there. Both maps take $D$ into $D$.

Coarse initialization gives $U_1^0=U_2^0=1\mathrm{/}4$, while the first corrected node is $U_1^1=F(1\mathrm{/}4)=1\mathrm{/}16$. Applying [F1] again, $U_2^1=G(1\mathrm{/}16)+F(1\mathrm{/}4)-G(1\mathrm{/}4)=1\mathrm{/}16+1\mathrm{/}16-1\mathrm{/}4=-1\mathrm{/}8$.

Since $-1\mathrm{/}8\mathrm{\notin }D$, the first corrected table already leaves the set on which the Lipschitz bounds were verified. Thus [F2] cannot be invoked for a sweep whose comparisons use that value; no divergence conclusion follows.

By [F1], each fine Euler step for $\dot{y}=-y$ multiplies by $\alpha =1-h=3\mathrm{/}4$. By [F2], a backward-Euler macro step solves $z=x-\frac{1}{2}z$, so its multiplier is $\psi =2\mathrm{/}3$.

In fine order the error operator is $A_t=\left(\begin{array}{cccc}1& 0& 0& 0\\ -\alpha & 1& 0& 0\\ 0& -\alpha & 1& 0\\ 0& 0& -\alpha & 1\end{array}\right)$. In F/C order $F=(1,3)$, $C=(2,4)$, its blocks are $A_{FF}=I$, $A_{FC}=\left(\begin{array}{cc}0& 0\\ -\alpha & 0\end{array}\right)$, $A_{CF}=\left(\begin{array}{cc}-\alpha & 0\\ 0& -\alpha \end{array}\right)$, and $A_{CC}=I$. Hence [F4] gives $S=\left(\begin{array}{cc}1& 0\\ -{\alpha }^2& 1\end{array}\right)$.

F-relaxation maps an error $(e_1,e_2,e_3,e_4)$ to $(0,e_2,\alpha e_2,e_4)$, so the F-row residuals vanish and the ideal restriction in [F5] reduces to the C residual $(e_2,e_4-{\alpha }^2{e}_2)$. Solving the practical coarse system $\left(\begin{array}{cc}1& 0\\ -\psi & 1\end{array}\right)z=(e_2,e_4-{\alpha }^2{e}_2)$ gives $z_1=e_2$, $z_2=e_4+(\psi -{\alpha }^2)e_2$. Subtracting the ideal interpolation [F5] leaves $(0,0,0,({\alpha }^2-\psi )e_2)$; post-F-relaxation leaves this vector unchanged.

Therefore $E$ has its only nonzero entry in row $4$, column $2$, equal to ${\alpha }^2-\psi =\frac{9}{16}-\frac{2}{3}=-\frac{5}{48}$. For the norm in [A1], $\mathrm{\parallel }Ee{\mathrm{\parallel }}_{\mathrm{\infty }}=\frac{5}{48}\mathrm{\mid }{e}_2\mathrm{\mid }\le \frac{5}{48}\mathrm{\parallel }e{\mathrm{\parallel }}_{\mathrm{\infty }}$, with equality when $e=(0,1,0,0)$. Thus $\mathrm{\parallel }E{\mathrm{\parallel }}_{\mathrm{\infty }}=5\mathrm{/}48<1$.

For every $e\in {\mathbb{R}}^4$, $\mathrm{\parallel }e{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_i\mathrm{\mid }{e}_i\mathrm{\mid }$ is nonnegative and vanishes only when every coordinate is zero; $\mathrm{\parallel }\lambda e{\mathrm{\parallel }}_{\mathrm{\infty }}=\mathrm{\mid }\lambda \mathrm{\mid }\mathrm{\parallel }e{\mathrm{\parallel }}_{\mathrm{\infty }}$; and $\mathrm{\parallel }e+f{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }e{\mathrm{\parallel }}_{\mathrm{\infty }}+\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty }}$. Thus the norm in [A1] satisfies [F7]. For any matrix $B$, $\mathrm{\parallel }Bv{\mathrm{\parallel }}_{\mathrm{\infty }}\le ({\max }_i{\sum }_j\mathrm{\mid }{B}_{ij}\mathrm{\mid })\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}$ by applying the finite triangle inequality to each row. The row sums of $A_t$ are at most $1+\alpha =7\mathrm{/}4$. If $A_{t}u=w$, forward substitution gives $u_1=w_1$ and $u_i=w_i+\alpha u_{i-1}$, hence by induction $u_i={\sum }_{j=1}^i{\alpha }^{i-j}{w}_j$. Therefore $A_t^{-1}$ has entries ${\alpha }^{i-j}$ for $i\ge j$ and zero otherwise, with row sums at most $1+\alpha +{\alpha }^2+{\alpha }^3=175\mathrm{/}64$. Thus $\mathrm{\parallel }{A}_t{\mathrm{\parallel }}_{\mathrm{\infty }}\le 7\mathrm{/}4$ and $\mathrm{\parallel }{A}_t^{-1}{\mathrm{\parallel }}_{\mathrm{\infty }}\le 175\mathrm{/}64$. All hypotheses of [F6] hold with $q=5\mathrm{/}48$, so the error after $r$ cycles is at most $(5\mathrm{/}48{)}^r$ times its initial value.