1 A detailed example↩︎

Here we include some equations and theorem-like environments to show how these are labeled in a supplement and can be referenced from the main text. Consider the following equation: \[\label{eq:suppa} a^2 + b^2 = c^2.\tag{1}\] You can also reference equations such as [eq:matrices] [eq:bb] from the main article in this supplement.

Here is an example citation: KoMa14?.

2 Proof of [thm:bigthm]↩︎

3 Additional experimental results↩︎

¿tbl:tab:foo? shows additional supporting evidence.

3.0.1 The case \(k=0\)↩︎

We begin by eliminating the index \(k+1\) on the right-hand side of the second equation in [eqn:coupled] through iterative substitution with respect to \(n\): \[\begin{align} \label{eqn:k610} E_{n+1}^{k+1}&=G_{1}^{2}E_{n-1}^{k+1}+\left( \bar{F}_{1} D_{n}^{k}+\gamma_{0} E_{n}^{k} \right) +G_{1}\left( \bar{F}_{1} D_{n-1}^{k}+\gamma_{0} E_{n-1}^{k} \right) \nonumber \\ &= G_{1}^{n+1} E_{0}^{k+1} + \sum_{i=0}^{n} G_{1}^{i} \left( \bar{F}_1 D_{n-i}^{k} + \gamma_{0} E_{n-i}^{k} \right), \end{align}\tag{2}\] where \(E_{0}^{k+1}=U_0^{k+1} - U_0=0\). Setting \(k=0\), we obtain: \[\begin{align} E_{n+1}^{1} &= \sum_{i=0}^{n} G_{1}^{i} \left( F_{1}^{(J)} \left( E_{n-i,-1}^{0} - E_{n-i}^{0} \right) + \gamma_{0} E_{n-i}^{0} \right) \\ &= \sum_{i=0}^{n} G_{1}^{i} F_{1}^{(J)} E_{n-i,-1}^{0} + \sum_{i=0}^{n} G_{1}^{i} \left( \gamma_{0} - F_{1}^{(J)} \right) E_{n-i}^{0}. \end{align}\] By taking the \(L^2\) norm on both sides, we derive the error bound for the case \(k=0\), \[\| E_{n+1}^{1}\|_{L^{2}} \leq \| F_{1}^{\left( J \right)}\|_{H} \sum_{i=0}^{n} \| E_{i,-1}^{0}\|_{L^{2}} +\| \gamma_{0} -F_{1}^{\left( J \right)}\|_{H} \sum_{i=0}^{n} \| E_{i}^{0}\|_{L^{2}},\] since \(\| G_1 \|_{H} \leq 1\).

3.0.2 The case \(k=1\)↩︎

We continue with 2 in the case \(k=0\). Then using the first equation in [eqn:coupled] to eliminate \(D_i^k\) on the right-hand side, \[\begin{align} E_{n+1}^{k+1} &= \gamma_{0} \sum_{i=0}^{n} G_{1}^{i}E_{n-i}^{k} + \bar{F_{1}} \sum_{i=0}^{n} G_{1}^{i}D_{n-i}^{k} \\ &= \gamma_{0} \sum_{i=0}^{n} G_{1}^{i}E_{n-i}^{k} + \bar{F_{1}} \sum_{i=0}^{n-1} G_{1}^{i}\left( hE_{n-i-1}^{k-1} + \gamma_{1} D_{n-i-1}^{k-1} \right), \end{align}\] where \(D_0^k = E_{0,-1}^k - E_0^k=0\). Our next target is to further expand \(E_i^k\) on the right-hand side. We have the expression for \(E_{n-i}^k\), \[\begin{align} E_{n-i}^{k} &= G_{1} E_{n-1-i}^{k} + \bar{F_{1}} D_{n-1-i}^{k-1} + \gamma_{0} E_{n-1-i}^{k-1} \\ &= G_{1}^{n-i} E_{0}^{k} + \sum_{j=0}^{n-1-i} G_{1}^{j} \left( \gamma_{0} E_{n-1-i-j}^{k-1} + \bar{F_{1}} D_{n-1-i-j}^{k-1} \right), \end{align}\] with \(E_0^k = U_0^k - U_0=0\). Then we continue our expression for the Parareal error \(E_{n+1}^{k+1}\): \[\begin{align} E_{n+1}^{k+1} &= \gamma_{0} \sum_{i=0}^{n} G_{1}^{i} \sum_{j=0}^{n-1-i} G_{1}^{j} \left( \gamma_{0} E_{n-1-i-j}^{k-1} + \bar{F_{1}} D_{n-1-i-j}^{k-1} \right) \nonumber \\ &\quad + \bar{F_{1}} h \sum_{i=0}^{n-1} G_{1}^{i} E_{n-1-i}^{k-1} + \bar{F_{1}} \gamma_{1} \sum_{i=0}^{n-1} G_{1}^{i} D_{n-1-i}^{k-1} \nonumber \\ &= \gamma_{0}^{2} \sum_{i=0}^{n} \sum_{j=0}^{n-1-i} G_{1}^{i+j} E_{n-1-i-j}^{k-1} + \gamma_{0} \bar{F_{1}} \sum_{i=0}^{n} \sum_{j=0}^{n-1-i} G_{1}^{i+j} D_{n-1-i-j}^{k-1} \nonumber \\ &\quad + \bar{F_{1}} h \sum_{i=0}^{n-1} G_{1}^{i} E_{n-1-i}^{k-1} + \bar{F_{1}} \gamma_{1} \sum_{i=0}^{n-1} G_{1}^{i} D_{n-1-i}^{k-1} \nonumber \\ &= \sum_{m=0}^{n-1} (m+1) G_{1}^{m} \gamma_{0}^{2} E_{n-1-m}^{k-1} + \gamma_{0} \bar{F_{1}} \sum_{m=0}^{n-1} (m+1) G_{1}^{m} D_{n-1-m}^{k-1} \nonumber\\ &\quad + \bar{F_{1}} h \sum_{i=0}^{n-1} G_{1}^{i} E_{n-1-i}^{k-1} + \bar{F_{1}} \gamma_{1} \sum_{i=0}^{n-1} G_{1}^{i} D_{n-1-i}^{k-1} \nonumber\\ &= \sum_{m=0}^{n-1} G_{1}^{m} \left( (m+1) \gamma_{0}^{2} + \bar{F_{1}} h \right) E_{n-1-m}^{k-1}\nonumber \\ &\quad + \sum_{m=0}^{n-1} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) D_{n-1-m}^{k-1}.\label{eqn:k611} \end{align}\tag{3}\] Note that the right-hand side of the equality above is only related to the iteration \(k-1\). Setting \(k=1\) into the equality above, we then obtain \[\begin{align} E_{n+1}^{2} &= \sum_{m=0}^{n-1} G_{1}^{m} \left( (m+1) \gamma_{0}^{2} + \bar{F}_{1} h \right) E_{n-1-m}^{0} \\ &\quad + \sum_{m=0}^{n-1} G_{1}^{m} \bar{F}_{1} \left( (m+1) \gamma_{0} + \gamma_{1} \right) \left( G_{1} G_{2}^{-1} E_{n-1-m,-1}^{0} - E_{n-1-m}^{0} \right) \\ &= \sum_{m=0}^{n-1} G_{1}^{m} \left( (m+1) \gamma_{0} \left( \gamma_{0} - \bar{F}_{1} \right) + \bar{F}_{1} \left( h - \gamma_{1} \right) \right) E_{n-1-m}^{0} \\ &\quad + \sum_{m=0}^{n-1} G_{1}^{m} \bar{F}_{1} \left( (m+1) \gamma_{0} + \gamma_{1} \right) G_{1} G_{2}^{-1} E_{n-1-m,-1}^{0}. \end{align}\] After taking the \(L^2\) norm on both sides, we then obtain \[\begin{align} \| E_{n+1}^{2}\|_{L^{2}} &\leq \| \sum_{m=0}^{n-1} G_{1}^{m}\left( \left( m+1 \right) \gamma_{0} \left( \gamma_{0} -\bar{F}_{1} \right) +\bar{F}_{1} \left( h-\gamma_{1} \right) \right) E_{n-1-m}^{0}\|_{L^{2}} \\ &\quad +\| \sum_{m=0}^{n-1} G_{1}^{m}\bar{F}_{1} \left( (m+1)\gamma_{0} +\gamma_{1} \right) G_{1}G_{2}^{-1}E_{n-1-m,-1}^{0}\|_{L^{2}}. \end{align}\] For the first term above, we have \[\begin{align} & \| \sum_{m=0}^{n-1} G_{1}^{m}\left( \left( m+1 \right) \gamma_{0} \left( \gamma_{0} -\bar{F}_{1} \right) +\bar{F}_{1} \left( h-\gamma_{1} \right) \right) E_{n-1-m}^{0}\|_{L^{2}} \\ & \leq \sup_{p\in \mathbb{N}^{+}} \sum_{m=0}^{n-1} |G_{1,p}^{m}\left( \left( m+1 \right) \gamma_{0,p} \left( \gamma_{0,p} -\bar{F}_{1,p} \right) +\bar{F}_{1,p} \left( h_{p}-\gamma_{1,p} \right) \right) |\sum_{i=0}^{n-1} \| E_{i}^{0}\|_{L^{2}} \end{align}\] Similarly, for the second term, we have \[\begin{align} & \left\| \sum_{m=0}^{n-1} G_{1}^{m}\bar{F}_{1} \left( (m+1)\gamma_{0} +\gamma_{1} \right) G_{1}G_{2}^{-1}E_{n-1-m,-1}^{0} \right\|_{L^{2}} \\ & \leq \sup_{p\in \mathbb{N}^{+}} \left| \sum_{m=0}^{n-1} G_{1,p}^{m}\bar{F}_{1,p} \left( \left( m+1 \right) \gamma_{0,p} +\gamma_{1,p} \right) G_{1,p}G_{2,p}^{-1} \right| \sum_{i=0}^{n-1} \left\| E_{i,-1}^{0} \right\|_{L^{2}}. \end{align}\] Then for \(k=1\), we have the following error estimate, \[\begin{align} \| E_{n+1}^{2} \|_{L^{2}} &\leq \sup_{p\in \mathbb{N}^{+}} \sum_{m=0}^{n-1} \left| G_{1,p}^{m}\left( (m+1) \gamma_{0,p} (\gamma_{0,p} -\bar{F}_{1,p}) + \bar{F}_{1,p} (h_{p}-\gamma_{1,p}) \right) \right| \sum_{i=0}^{n-1} \| E_{i}^{0} \|_{L^{2}} \\ &\quad + \sup_{p\in \mathbb{N}^{+}} \left| \sum_{m=0}^{n-1} G_{1,p}^{m}\bar{F}_{1,p} \left( (m+1)\gamma_{0,p} + \gamma_{1,p} \right) G_{1,p}G_{2,p}^{-1} \right| \sum_{i=0}^{n-1} \left\| E_{i,-1}^{0} \right\|_{L^{2}}. \end{align}\]

3.0.3 The case \(k=2\)↩︎

We continue with 3 in the case \(k=1\). Using the coupled equations [eqn:coupled], \[\begin{align} E_{n+1}^{k+1} &= \sum_{m=0}^{n-1} G_{1}^{m}\left( \left( m+1 \right) \gamma_{0}^{2} + \bar{F}_{1} h \right) E_{n-1-m}^{k-1} \\ &\quad + \sum_{m=0}^{n-2} G_{1}^{m}\bar{F}_{1} \left( \left( m+1 \right) \gamma_{0} + \gamma_{1} \right) \left( \gamma_{1} D_{n-2-m}^{k-2} + h E_{n-2-m}^{k-2} \right). \end{align}\] We then further expand \(E_{n-1-m}^{k-1}\) and set \(k=2\) to obtain \[\begin{align} E_{n+1}^{3} &= \sum_{m=0}^{n-1} \sum_{j=0}^{n-2-m} G_{1}^{m+j}\left( \left( m+1 \right) \gamma_{0}^{2} +\bar{F}_{1} h \right) \left( \bar{F}_{1} D_{n-2-m-j}^{0}+\gamma_{0} E_{n-2-m-j}^{0} \right) \\ &\quad +\sum_{m=0}^{n-2} G_{1}^{m}\bar{F}_{1} \left( \left( m+1 \right) \gamma_{0} +\gamma_{1} \right) \left( \gamma_{1} D_{n-2-m}^{0}+hE_{n-2-m}^{0} \right) \\ &= \sum_{i=0}^{n-2} G_{1}^{i}\left( \sum_{m=0}^{i} \left( \left( m+1 \right) \gamma_{0}^{2} +\bar{F}_{1} h \right) \right) \left( \bar{F}_{1} D_{n-2-i}^{0}+\gamma_{0} E_{n-2-i}^{0} \right) \\ &\quad +\sum_{m=0}^{n-2} G_{1}^{m}\bar{F}_{1} \left( \left( m+1 \right) \gamma_{0} +\gamma_{1} \right) \left( \gamma_{1} D_{n-2-m}^{0}+hE_{n-2-m}^{0} \right) \\ &= \sum_{i=0}^{n-2} G_{1}^{i} \left( \bar{F}_{1} \left( \left( i+1 \right) \left( \frac{\gamma_{0}^{2} \left( i+2 \right)}{2} +\bar{F}_{1} h+\gamma_{0} \gamma_{1} \right) +\gamma_{1}^{2} \right) D_{n-2-i}^{0} \right. \\ &\quad \left. + \left( \left( i+1 \right) \frac{\gamma_{0}^{3} \left( i+2 \right)}{2} +2\left( i+1 \right) \bar{F}_{1} h\gamma_{0} +\bar{F}_{1} h\gamma_{1} \right) E_{n-2-i}^{0} \right). \end{align}\]

4 Linear Convergence for the Linear Parabolic Problem↩︎

4.1 Preliminaries↩︎

Consider the following linear parabolic problem \[\left \{ \begin{align} u' (t)+ A u(t) &= f(t), \quad 0<t<T,\\ u(0)&=u_0 . \end{align}\right .\] Thanks to Lemma 10.3 in thomee2007galerkin?, we are able to give the explicit formula of our FPs: \[\begin{align} &F\left( T_{0}+n\Delta t,T_{0}+(q-1)\Delta t,u_{0},\cdots ,u_{q-1} \right) \\ &= \sum_{s=0}^{q-1} \beta_{ns} \left( \Delta tA \right) u_{s} + \Delta t\sum_{j=q}^{n} \beta_{n-j} \left( \Delta tA \right) f\left( T_{0}+j\Delta t \right) \\ &:= \sum_{s=0}^{q-1} F_{s}^{\left( n-q+1 \right)}(\Delta t A) u_{s} + N^{\left( n-q+1 \right)}\left( f \right) \left( T_{0}+(q-1)\Delta t \right), \end{align}\] where the \(\beta_j(\lambda)\) and \(\beta_{ns}(\lambda)\) are defined by

\[\widetilde{\beta}(s)=\sum_{j = 0}^{\infty}\beta_j(\lambda)\zeta^j := (\widetilde{\alpha}(\zeta)+\lambda)^{-1}, \quad \beta_{ns}(\lambda)=-\sum_{j = q - s}^{q}\beta_{n - s - j}(\lambda)\alpha_j,\] with \(\tilde{\alpha} \left( \zeta \right) =\alpha_{j} \zeta^{j}\), where the \(\alpha_j\) are the coefficients defined by \(\tilde{\partial_{q}} U^{n}=\frac{1}{\Delta t} \sum_{j=0}^{q} \alpha_{j} U^{n-j}\).

For convenience, we define several rational functions, \[h_1(z) = \max_{0 \leq i \leq q-1} \left| \sum_{s=0}^{q-1} \Big( F_{s}^{(J-i)}(z) - F_{s}^{(J)}(z) \Big) \right|,~\gamma_1(z) = \max_{0 \leq i \leq q-1} \left| F_{s}^{(J-i)}(z) - F_{s}^{(J)}(z) \right|,\] \[\gamma_0 (z) = \sum_{s=0}^{q-1} F_{s}^{\left( J \right)}\left( z \right) -R\left( Jz \right),~C^{(J)} (z)=\max_{1\leq s\leq q-1} |F_{s}^{\left( J \right)}\left( z \right) |.\]

Without loss of generality, we consider the linear problem, \(u'+ Au=0\) and the BDF2 scheme as FPs in the Parareal algorithm. Then the multi-step Parareal can be expressed as \[\begin{align} \left\{ \begin{aligned} U_{n+1}^{k+1}&=G_{1}\left( U_{n}^{k+1} \right) +F_{1}\left( U_{n,-1}^{k} \right) +F_{2}\left( U_{n}^{k} \right) -G_{1}\left( U_{n}^{k} \right), \\ U_{n+1,-1}^{k+1}&=G_{2}\left( U_{n}^{k+1} \right) +F_{1}^{\prime}\left( U_{n,-1}^{k} \right) +F_{2}'\left( U_{n}^{k} \right) -G_{2}\left( U_{n}^{k} \right). \end{aligned} \right. \end{align}\] The exact solution also satisfies \[\begin{align} \left\{ \begin{aligned} U_{n+1} &= F_{1}\left( U_{n,-1} \right) + F_{2}\left( U_{n} \right), \\ U_{n+1,-1} &= F_{1}^{\prime}\left( U_{n,-1} \right) + F_{2}^{\prime}\left( U_{n} \right). \end{aligned} \right. \end{align}\] Thus, we define the Parareal error \(E_n^k = U_n^k - U_n\) and \(E_{n,-1}^k = U_{n,-1}^k - U_{n,-1}\), which satisfy \[\begin{align} \left\{ \begin{aligned} E_{n+1}^{k+1}&=G_{1}\left( E_{n}^{k+1} \right) +F_{1}\left( E_{n,-1}^{k} \right) +F_{2}\left( E_{n}^{k} \right) -G_{1}\left( E_{n}^{k} \right), \\ E_{n+1,-1}^{k+1}&=G_{2}\left( E_{n}^{k+1} \right) +F_{1}^{\prime}\left( E_{n,-1}^{k} \right) +F_{2}'\left( E_{n}^{k} \right) -G_{2}\left( E_{n}^{k} \right). \end{aligned} \right. \end{align}\] If \(G_2\) is invertible, the second equation in [eqn:para_err] is equal to \[G_{1}G_{2}^{-1}\left( E_{n+1,-1}^{k+1} \right) =G_{1}\left( E_{n}^{k+1} \right) +G_{1}G_{2}^{-1}F_{1}^{\prime}\left( E_{n,-1}^{k} \right) +G_{1}G_{2}^{-1}F_{2}^{\prime}\left( E_{n}^{k} \right) -G_{1}\left( E_{n}^{k} \right).\] Given that \(F_1',~F_2'\), and \(G_1 G_2^{-1}\) mutually commute, this can be rewritten as \[G_{1}G_{2}^{-1}\left( E_{n+1,-1}^{k+1} \right) =G_{1}\left( E_{n}^{k+1} \right) +F_{1}^{\prime}G_{1}G_{2}^{-1}\left( E_{n,-1}^{k} \right) +F_{2}^{\prime}G_{1}G_{2}^{-1}\left( E_{n}^{k} \right) -G_{1}\left( E_{n}^{k} \right).\] We further introduce one new variable, \(D_{n}^{k}=G_{1}G_{2}^{-1}\left( E_{n,-1}^{k} \right) -E_{n}^{k}\), which satisfies \[\begin{align} D_{n+1}^{k+1} &= \left( F_{1}^{\prime}G_{1}G_{2}^{-1}-F_{1} \right) \left( E_{n,-1}^{k} \right) +\left( F_{2}'{ G_{1}G_{2}^{-1}}-F_{2} \right) \left( E_{n}^{k} \right) \nonumber \\ &= \left( F_{1}^{\prime}-F_{1}G_{2}G_{1}^{-1} \right) \left( G_{1}G_{2}^{-1}\left( E_{n,-1}^{k} \right) -E_{n}^{k} \right) \nonumber \\ &\quad +\left( F_{1}^{\prime}+F_{2}^{\prime}G_{1}G_{2}^{-1}-F_{1}G_{2}G_{1}^{-1}-F_{2} \right) \left( E_{n}^{k} \right) \nonumber \\ &:= \gamma_{1} D_{n}^{k}+hE_{n}^{k}. \end{align}\] The Parareal error \(E_{n+1}^{k+1}\) can also be related with \(D_n^k\) through \[\begin{align} E_{n+1}^{k+1} &= G_{1}\left( E_{n}^{k+1} \right) + F_{1}G_{2}G_{1}^{-1}\left( G_{1}G_{2}^{-1}\left( E_{n,-1}^{k} \right) - E_{n}^{k} \right) \\ &\quad + \left( F_{1}G_{2}G_{1}^{-1} + F_{2} - G_1 \right) \left( E_{n}^{k} \right) \\ &:= G_{1} E_{n}^{k+1} + \bar{F_1} D_{n}^{k} + \gamma_{0} E_{n}^{k}. \end{align}\] Then we derive the coupled equations between \(E_n^k\) and \(D_n^k\): \[\left\{ \begin{align} D_{n+1}^{k+1} &= \gamma_{1} D_{n}^{k} + h E_{n}^{k}, \\ E_{n+1}^{k+1} &= G_{1} E_{n}^{k+1} + \bar{F}_{1} D_{n}^{k} + \gamma_{0} E_{n}^{k}. \end{align} \right.\] Our further estimate bases on these coupled equations. Now we start from eliminating the index \(k+1\) of the right-hand side of the second equation in [eqn:coupled] by iterating itself on \(n\), \[\begin{align} E_{n+1}^{k+1} &= G_{1}^{2} E_{n-1}^{k+1} + \sum_{i=0}^{1} G_{1}^{i}\left( \bar{F}_1 D_{n-i}^{k} + \gamma_{0} E_{n-i}^{k} \right) \\ &= G_{1}^{n+1} E_{0}^{k+1} + \sum_{i=0}^{n} G_{1}^{i}\left( \bar{F}_1 D_{n-i}^{k} + \gamma_{0} E_{n-i}^{k} \right), \end{align}\] where \(E_{0}^{k+1}=U_{0}^{k+1}-U_{0}=0\). Then using the first equation in [eqn:coupled] to eliminate \(D_i^k\) on the right-hand side, \[\begin{align} E_{n+1}^{k+1} &= \gamma_{0} \sum_{i=0}^{n} G_{1}^{i}E_{n-i}^{k} + \bar{F_{1}} \sum_{i=0}^{n} G_{1}^{i}D_{n-i}^{k} \\ &= \gamma_{0} \sum_{i=0}^{n} G_{1}^{i}E_{n-i}^{k} + \bar{F_{1}} \sum_{i=0}^{n} G_{1}^{i}\left( hE_{n-i-1}^{k-1} + \gamma_{1} D_{n-i-1}^{k-1} \right). \end{align}\] Our next target is to further expand \(E_i^k\) on the right-hand side, because the numerical experiments indicate that we should derive staggered time steps, and if we don’t follow this rule, our estimate is not accurate enough. We have the expression for \(E_{n-i}^k\), \[\begin{align} E_{n-i}^{k} &= G_{1} E_{n-1-i}^{k} + \bar{F_{1}} D_{n-1-i}^{k-1} + \gamma_{0} E_{n-1-i}^{k-1} \\ &= G_{1}^{n-i} E_{0}^{k} + \sum_{j=0}^{n-i} G_{1}^{j} \left( \gamma_{0} E_{n-1-i-j}^{k-1} + \bar{F_{1}} D_{n-1-i-j}^{k-1} \right), \end{align}\] with \(E_0^k = U_0^k - U_0=0\). Then we continue our expression for the Parareal error \(E_{n+1}^{k+1}\): \[\begin{align} E_{n+1}^{k+1} &= \gamma_{0} \sum_{i=0}^{n} G_{1}^{i} \sum_{j=0}^{n-i} G_{1}^{j} \left( \gamma_{0} E_{n-1-i-j}^{k-1} + \bar{F_{1}} D_{n-1-i-j}^{k-1} \right) \\ &\quad + \bar{F_{1}} h \sum_{i=0}^{n} G_{1}^{i} E_{n-1-i}^{k-1} + \bar{F_{1}} \gamma_{1} \sum_{i=0}^{n} G_{1}^{i} D_{n-1-i}^{k-1} \\ &= \gamma_{0}^{2} \sum_{i=0}^{n} \sum_{j=0}^{n-i} G_{1}^{i+j} E_{n-1-i-j}^{k-1} + \gamma_{0} \bar{F_{1}} \sum_{i=0}^{n} \sum_{j=0}^{n-i} G_{1}^{i+j} D_{n-1-i-j}^{k-1} \\ &\quad + \bar{F_{1}} h \sum_{i=0}^{n} G_{1}^{i} E_{n-1-i}^{k-1} + \bar{F_{1}} \gamma_{1} \sum_{i=0}^{n} G_{1}^{i} D_{n-1-i}^{k-1} \\ &= \gamma_{0} \sum_{m=0}^{n} (m+1) G_{1}^{m} \gamma_{0}^{2} E_{n-1-m}^{k-1} + \gamma_{0} \bar{F_{1}} \sum_{m=0}^{n} (m+1) G_{1}^{m} D_{n-1-m}^{k-1} \\ &\quad + \bar{F_{1}} h \sum_{i=0}^{n} G_{1}^{i} E_{n-1-i}^{k-1} + \bar{F_{1}} \gamma_{1} \sum_{i=0}^{n} G_{1}^{i} D_{n-1-i}^{k-1} \\ &= \sum_{m=0}^{n} G_{1}^{m} \left( (m+1) \gamma_{0}^{2} + \bar{F_{1}} h \right) E_{n-1-m}^{k-1} \\ &\quad + \sum_{m=0}^{n} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) D_{n-1-m}^{k-1}. \end{align}\] Note that the right-hand side of the equality above is only related to the iteration \(k-1\). Now we further expand \(D_{n-1-m}^{k-1}\) to iteration \(k-3\) based on [eqn:coupled]: \[\begin{align} D_{n-1-m}^{k-1} &= h E_{n-2-m}^{k-2} + \gamma_{1} D_{n-2-m}^{k-2} \\ &= h \left( G_{1} E_{n-3-m}^{k-2} + \gamma_{0} E_{n-3-m}^{k-3} + \bar{F_{1}} D_{n-3-m}^{k-3} \right) + \gamma_{1} D_{n-2-m}^{k-2} \\ &= h \sum_{j=0}^{n-3-m} G_{1}^{j} \left( \gamma_{0} E_{n-3-m-j}^{k-3} + \bar{F_{1}} D_{n-3-m-j}^{k-3} \right) + \gamma_{1} D_{n-2-m}^{k-2}. \end{align}\] Then we further expand \(D_{n-2-m}^{k-2}\) to eliminate iteration \(k-2\) on the right-hand side of the above equation, \[\begin{align} D_{n-1-m}^{k-1} &= h \sum_{j=0}^{n-3-m} G_{1}^{j} \left( \gamma_{0} E_{n-3-m-j}^{k-3} + \bar{F_{1}} D_{n-3-m-j}^{k-3} \right) + \gamma_{1} h E_{n-3-m}^{k-3} + \gamma_{1}^{2} D_{n-3-m}^{k-3} \\ &= h \gamma_{0} \sum_{j=0}^{n-3-m} G_{1}^{j} E_{n-3-m-j}^{k-3} + \gamma_{1} h E_{n-3-m}^{k-3} + h \bar{F_{1}} \sum_{j=0}^{n-3-m} G_{1}^{j} D_{n-3-m-j}^{k-3} + \gamma_{1}^{2} D_{n-3-m}^{k-3}. \end{align}\] Finally, we take the expression of \(D_{n-1-m}^{k-1}\) back to the Parareal error \(E_{n+1}^{k+1}\), \[\begin{align} E_{n+1}^{k+1} &= \sum_{m=0}^{n} G_{1}^{m} \left( (m+1) \gamma_{0}^{2} + \bar{F_{1}} h \right) E_{n-1-m}^{k-1} \\ &\quad + \sum_{m=0}^{n} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) h \left( \gamma_{0} \sum_{j=0}^{n-3-m} G_{1}^{j} E_{n-3-m-j}^{k-3} + \gamma_{1} E_{n-3-m}^{k-3} \right) \\ &\quad + \sum_{m=0}^{n} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) \left( h \bar{F_{1}} \sum_{j=0}^{n-3-m} G_{1}^{j} D_{n-3-m-j}^{k-3} + \gamma_{1}^{2} D_{n-3-m}^{k-3} \right). \end{align}\] Now we take a close look at the equation above. The first row involves \(E_i^{k-1}\), the second row involves \(E_i^{k-3}\), and the third row involves \(D_i^{k-3}\). To analyze the \(L^2\) norm of \(E_{n+1}^{k+1}\), we consider the \(p\)-th spectrum of the elliptic operator \(A\) and take the inner product with the eigenfunction \(\lambda_p\). \[\begin{align} (E_{n+1}^{k+1},\lambda_p) &= \sum_{m=0}^{n} G_{1}^{m} \left( (m+1) \gamma_{0}^{2} + \bar{F_{1}} h \right) (E_{n-1-m}^{k-1},\lambda_p) \\ &\quad + \sum_{m=0}^{n} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) h \left( \gamma_{0} \sum_{j=0}^{n-3-m} G_{1}^{j} (E_{n-3-m-j}^{k-3},\lambda_p) + \gamma_{1} (E_{n-3-m}^{k-3},\lambda_p) \right) \\ &\quad + \sum_{m=0}^{n} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) \left( h \bar{F_{1}} \sum_{j=0}^{n-3-m} G_{1}^{j} (D_{n-3-m-j}^{k-3},\lambda_p) + \gamma_{1}^{2} (D_{n-3-m}^{k-3},\lambda_p) \right). \end{align}\] Let \(e_n^k=(E_n^k,\lambda_p)\) and \(d_n^k = (D_n^k,\lambda_p)\). We omit the explicit dependence of \(e_n^k\), \(d_n^k\) and all the operators appear above on \(p\) for brevity. \[\begin{align} e_{n+1}^{k+1} &= \sum_{m=0}^{n} G_{1}^{m} \left( (m+1) \gamma_{0}^{2} + \bar{F_{1}} h \right) e_{n-1-m}^{k-1} \\ &\quad + \sum_{m=0}^{n} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) h \left( \gamma_{0} \sum_{j=0}^{n-3-m} G_{1}^{j} e_{n-3-m-j}^{k-3} + \gamma_{1} e_{n-3-m}^{k-3} \right) \\ &\quad + \sum_{m=0}^{n} G_{1}^{m} \bar{F_{1}} \left( (m+1) \gamma_{0} + \gamma_{1} \right) \left( h \bar{F_{1}} \sum_{j=0}^{n-3-m} G_{1}^{j} d_{n-3-m-j}^{k-3} + \gamma_{1}^{2} d_{n-3-m}^{k-3} \right). \end{align}\]

(Term I) This term represents the primary error component of \(E_{n+1}^{k+1}\), as it incorporates the complete error propagation from the \((k-1)\)-th iteration. \[\begin{align} \left| \sum_{m=0}^{n} G_{1}^{m}\left( (m+1)\gamma_{0}^{2} +\bar{F_{1}} h \right) e_{n-1-m}^{k-1}\right| &\leq \max_{i} |e_{i}^{k-1}|\sum_{m=0}^{n} |G_{1}|^{m}\left| (m+1) \gamma_{0}^{2} +\bar{F_{1}} h\right| \\ &\leq \gamma_{a,p} \max_{i} |e_{i}^{k-1}|. \end{align}\] We have to make this bound clear: \[\label{eqn:g95a} \gamma_{a,p}:=\sum_{m=0}^{n} |G_{1}|^{m}\left| (m+1) \gamma_{0,p}^{2} +\bar{F_{1}} h_p\right|.\tag{4}\]

\[\gamma_{a,p} :=\left( \frac{\gamma_{0,p}}{1-|G_{1}\left( Jz_{p} \right) |} \right)^{2} +\frac{|\bar{F}_{1,p} h_{p}|}{1-|G_{1}\left( Jz_{p} \right) |},\] where \(z_p = \Delta t\lambda_p\) and \[\begin{align} \gamma_{0,p} &= \left| \left( F_{1}(z_{p}) G_{2}(Jz_{p}) G_{1}^{-1}(Jz_{p}) + F_{2}(z_{p}) \right) - G_{1}(Jz_{p}) \right|, \\ \bar{F}_{1,p} &= |F_{1}(z_{p}) G_{2}(Jz_{p}) G_{1}^{-1}(Jz_{p})|, \\ h_{p} &= \left| F_{1}'(z_{p}) + F_{2}'(z_{p}) G_{1}(Jz_{p})G_2^{-1}(Jz_p) - F_{1}(z_{p}) G_{2}(Jz_{p}) G_{1}^{-1}(Jz_{p}) - F_{2}(z_{p}) \right|. \end{align}\]

(Term II) We bound for the second summation: \[\begin{align} &\left| h\gamma_{0} \bar{F_{1}} \sum_{m=0}^{n} \sum_{j=0}^{n-3-m} G_{1}^{m+j}\left( \left( m+1 \right) \gamma_{0} +\gamma_{1} \right) e_{n-3-m-j}^{k-3} \right. \\ &\quad \left. + h\gamma_{1} \bar{F_{1}} \sum_{m=0}^{n} G_{1}^{m}\left( \left( m+1 \right) \gamma_{0} +\gamma_{1} \right) e_{n-3-m}^{k-3} \right| \\ &\leq \max_{i} |e_{i}^{k-3}| \left( |h\gamma_{0} \bar{F_{1}} |\sum_{m=0}^{n} \sum_{j=0}^{n-3-m} |G_{1}|^{m+j}|\left( m+1 \right) \gamma_{0} +\gamma_{1} | \right) \\ &\quad + \max_{i} |e_{i}^{k-3}| \left( |h\gamma_{1} \bar{F_{1}} |\sum_{m=0}^{n} |G_{1}|^{m}|\left( m+1 \right) \gamma_{0} +\gamma_{1} | \right) \\ &\leq \left( \frac{|\bar{F_{1}} h\gamma_{0}^{2} |}{\left( 1-|G_{1}| \right)^{3}} + \frac{|\bar{F_{1}} h\gamma_{0} \gamma_{1} |}{\left( 1-|G_{1}| \right)^{2}} \right) \max_{i} |e_{i}^{k-3}| \\ &\quad + \left( \frac{|\bar{F_{1}} h\gamma_{0} \gamma_{1} |}{\left( 1-|G_{1}| \right)^{2}} + \frac{|\bar{F_{1}} h\gamma_{1}^{2} |}{1-|G_{1}|} \right) \max_{i} |e_{i}^{k-3}| \\ &\leq \frac{|\bar{F_{1}} h|}{1-|G_{1}|} \left( |\gamma_{1} |+\frac{|\gamma_{0} |}{1-|G_{1}|} \right)^{2} \max_{i} |e_{i}^{k-3}|. \end{align}\] We should make the bound clear: \[\label{eqn:g95b} \gamma_{b,p} :=\frac{\bar{F}_{1,p} h_{p}}{1-|G_{1}\left( Jz_{p} \right) |} \left( \gamma_{1,p} +\frac{\gamma_{0,p}}{1-|G_{1}\left( Jz_{p} \right) |} \right)^{2},\tag{5}\] where \[\gamma_{1,p} =|F_{1}^{\prime}(z_{p})-F_{1}(z_{p})G_{2}(Jz_{p})G_{1}^{-1}(Jz_{p})|.\]

(Term III) We analyze the final summation term, specifically examining the misalignment-induced error \(d_i^{k-3}\). Our approach involves expressing \(d_i^{k+1}\) in terms of \(d_i^{k-1}\) and \(e_i^{k-1}\), which enables us to establish an upper bound for \(d_i^{k+1}\). We start from [eqn:coupled], \[\begin{align} d_{n+1}^{k+1} &= h e_{n}^{k} + \gamma_{1} d_{n}^{k} \\ &= h \left( G_{1} e_{n-1}^{k} + \gamma_{0} e_{n-1}^{k-1} + \bar{F_{1}} d_{n-1}^{k-1} \right) + \gamma_{1} d_{n}^{k} \\ &= h \sum_{j=0}^{n-1} G_{1}^{j} \left( \gamma_{0} e_{n-1-j}^{k-1} + \bar{F_{1}} d_{n-1-j}^{k-1} \right) + +\gamma_{1} d_{n}^{k}. \end{align}\] Then we further expand \(d_n^k\) with \(d_{n}^{k}=he_{n-1}^{k-1}+\gamma_{1} d_{n-1}^{k-1}\), \[\begin{align} d_{n+1}^{k+1} &= h\sum_{j=0}^{n-1} G_{1}^{j}\left(\gamma_{0} e_{n-1-j}^{k-1} + \bar{F_{1}} d_{n-1-j}^{k-1}\right) + \gamma_{1}\left(he_{n-1}^{k-1} + \gamma_{1} d_{n-1}^{k-1}\right) \\ &= h\gamma_{0} \sum_{j=1}^{n-1} G_{1}^{j}e_{n-1-j}^{k-1} + h(\gamma_{1}+\gamma_0) e_{n-1}^{k-1}+ h\bar{F_{1}} \sum_{j=1}^{n-1} G_{1}^{j}d_{n-1-j}^{k-1} + (h\bar{F}_1+\gamma_{1}^{2}) d_{n-1}^{k-1}. \end{align}\] We take the absolute norm on both sides and derive the bound for \(d_{n+1}^{k+1}\), \[\begin{align} |d_{n+1}^{k+1}| &\leq \left( \frac{|G_{1} h \gamma_{0}|}{1 - |G_{1}|} + |h (\gamma_{0} + \gamma_{1})| \right) \max_{i} |e_{i}^{k-1}| + \left( \frac{|G_{1} h \bar{F}_{1}|}{1 - |G_{1}|} + |h \bar{F}_{1} + \gamma_{1}^{2}| \right) \max_{i} |d_{i}^{k-1}|\\ &:= \gamma_{d,p}\max_{i}|e_i^{k-1}| + \gamma_{e,p} \max_{i} |d_i^{k-1}|, \end{align}\] where we define the linear bounds, \[\label{eqn:g95d44d95e} \gamma_{d,p} =\frac{|G_{1}\left( Jz_{p} \right) h_{p}\gamma_{0,p} |}{1-|G_{1}\left( Jz_{p} \right) |} +|h_{p}\left( \gamma_{0,p} +\gamma_{1,p} \right) |,~\gamma_{e,p} =\frac{|G_{1}\left( Jz_{p} \right) h_{p}\bar{F}_{1,p} |}{1-|G_{1}\left( Jz_{p} \right) |} +|h_{p}\bar{F}_{1,p} +\gamma_{1,p}^{2} |.\tag{6}\] Then we derive the bound for the last summation, \[\begin{align} &\left| \sum_{m=0}^{n} G_{1}^{m}\bar{F}_{1} \left( (m+1)\gamma_{0} + \gamma_{1} \right) \left( h\bar{F}_{1} \sum_{j=0}^{n-3-m} G_{1}^{j}d_{n-3-m-j}^{k-3} + \gamma_{1}^{2} d_{n-3-m}^{k-3} \right) \right| \\ &\leq \left| h\bar{F}_{1}^{2} \sum_{m=0}^{n} \sum_{j=0}^{n-3-m} G_{1}^{m+j} \left( (m+1)\gamma_{0} + \gamma_{1} \right) d_{n-3-m-j}^{k-3} \right| \\ &\quad + \left| \gamma_{1}^{2} \bar{F}_{1} \sum_{m=0}^{n} G_{1}^{m} \left( (m+1)\gamma_{0} + \gamma_{1} \right) d_{n-3-m}^{k-3} \right| \\ &\leq \left( \frac{|h\bar{F}_{1}^{2} \gamma_{0}|}{(1-|G_{1}|)^{3}} + \frac{|h\bar{F}_{1}^{2} \gamma_{1}|}{(1-|G_{1}|)^{2}} \right) \max_{i} |d_{i}^{k-3}| + \left( \frac{|\bar{F}_{1} \gamma_{0} \gamma_{1}^{2}|}{(1-|G_{1}|)^{2}} + \frac{|\bar{F}_{1} \gamma_{1}^{3}|}{1-|G_{1}|} \right) \max_{i} |d_{i}^{k-3}|\\ &= \left( \frac{|h\bar{F}_{1}^{2} \gamma_{0}|}{(1-|G_{1}|)^{3}} + \frac{|h\bar{F}_{1}^{2} \gamma_{1}|}{(1-|G_{1}|)^{2}} + \frac{|\bar{F}_{1} \gamma_{0} \gamma_{1}^{2}|}{(1-|G_{1}|)^{2}} + \frac{|\bar{F}_{1} \gamma_{1}^{3}|}{1-|G_{1}|} \right) \max_{i} |d_{i}^{k-3}|. \end{align}\] Then we clarify the bound, but this is a little bit complicated, \[\label{eqn:g95c} \gamma_{c,p} =\frac{h_{p}\bar{F}_{1,p}^{2} \gamma_{0,p}}{\left( 1-|G_{1}\left( Jz_{p} \right) | \right)^{3}} +\frac{h_{p}\bar{F}_{1,p}^{2} \gamma_{1,p}}{\left( 1-|G_{1}\left( Jz_{p} \right) | \right)^{2}} +\frac{\bar{F}_{1,p} \gamma_{0,p} \gamma_{1,p}^{2}}{\left( 1-|G_{1}\left( Jz_{p} \right) | \right)^{2}} +\frac{\bar{F}_{1,p} \gamma_{1,p}^{3}}{1-|G_{1}\left( Jz_{p} \right) |}.\tag{7}\]

Finally, we arrive at the iteration on index \(k\), based on the estimates of the three terms: \[\begin{align} \left\{ \begin{aligned} |e_{n+1}^{k+1}| &\leq \gamma_{a,p} \max_{i} |e_{i}^{k-1}| + \gamma_{b,p} \max_{i} |e_{i}^{k-3}| + \gamma_{c,p} \max_{i} |d_{i}^{k-3}|, \\ |d_{n}^{k-1}| &\leq \gamma_{d,p} \max_{i} |e_{i}^{k-3}| + \gamma_{e,p} \max_{i} |d_{i}^{k-3}|, \end{aligned} \right. \end{align}\] where the left-hand side of the first equation is independent of \(n\), then we take the maximum over \(n\). We further introduce \(x_k=\max_{i}|e_i^{k}|\) and \(y_k = \max_{i} |d_i^k|\) and obtain \[\begin{align} \label{eqn:bound} \left\{ \begin{aligned} x_{k+1} &\leq \gamma_{a,p} x_{k-1} + \gamma_{b,p} x_{k-3} + \gamma_{c,p} y_{k-3}, \\ y_{k-1} &\leq \gamma_{d,p} x_{k-3} + \gamma_{e,p} y_{k-3}. \end{aligned} \right. \end{align}\tag{8}\] Next we study the recursion, \[\begin{align} x_{k+1} &\leq \gamma_{a,p} x_{k-1}+\gamma_{b,p} x_{k-3}+\gamma_{c,p} \left( \gamma_{d,p} x_{k-5}+\gamma_{e,p} y_{k-5} \right) \\ &\leq \gamma_{a,p} x_{k-1}+\gamma_{b,p} x_{k-3}+\gamma_{c,p} \gamma_{d,p} x_{k-5}+\gamma_{c,p} \gamma_{e,p} y_{k-5} \\ &\leq \gamma_{a,p} x_{k-1}+\gamma_{b,p} x_{k-3}+\gamma_{c,p} \gamma_{d,p} x_{k-5}+\gamma_{c,p} \gamma_{e,p} \left( \gamma_{d,p} x_{k-7}+\gamma_{e,p} y_{k-7} \right) \\ &\leq \gamma_{a,p} x_{k-1}+\gamma_{b,p} x_{k-3}+\gamma_{c,p} \gamma_{d,p} \left( x_{k-5}+\gamma_{e,p} x_{k-7} \right) +\gamma_{c,p} \gamma_{e,p}^{2} y_{k-7} \\ &\leq \gamma_{a,p} x_{k-1}+\gamma_{b,p} x_{k-3}+\gamma_{c,p} \gamma_{d,p} \sum_{i=0}^{\lfloor \frac{k-5}{2} \rfloor} \gamma_{e,p}^{i} x_{k-5-2i}+\gamma_{c,p} \gamma_{e,p}^{\lfloor \frac{k-5}{2} \rfloor +1} y_{k-5-2\lfloor \frac{k-5}{2} \rfloor}. \end{align}\]

4.1.1 Special case↩︎

If \(G_2\) is not invertible in [eqn:para_err], we first take the inner product of both sides with \(\lambda_p\), \[\begin{align} \left\{ \begin{aligned} e_{n+1}^{k+1} &= G_{1}(Jz_{p}) e_{n}^{k+1} + F_{1}(z_{p}) e_{n,-1}^{k} + F_{2}(z_{p}) e_{n}^{k} - G_{2}(Jz_{p}) e_{n}^{k}, \\ e_{n+1,-1}^{k+1} &= G_{2}(Jz_{p}) e_{n}^{k+1} + F_{1}'(z_{p}) e_{n,-1}^{k} + F_{2}'(z_{p}) e_{n}^{k} - G_{2}(Jz_{p}) e_{n}^{k}. \end{aligned} \right. \end{align}\] We consider the case when \(G_2(Jz_p)=0\), then the equations above reduce to XXX.

4.2 Comparison↩︎

The theoretical estimate is almost done, only the last step left. In this section, we compare the convergence rate between the multi-step Parareal by Maday and by our newly proposed update, through 8 . In Maday’s work, they choose \(G_1 = G_2=R(\Delta TA)\) in [eqn:m-para]. We propose a more reasonable update: \(G_1=R(\Delta TA)\) and \(G_2 = R((\Delta T-\Delta t)A)\) in [eqn:m-para]. Next, we will illustrate these two algorithms through the recursion 8 .

4.2.1 \(\gamma_{a,p}\)↩︎

The expression of the convergence function \(\gamma_{a,p}\) is given in 4 . This can be further bounded by \[\gamma_{a,p} \leq\left( \frac{\gamma_{0,p}}{1-|G_{1}\left( Jz_{p} \right) |} \right)^{2} +\frac{|\bar{F}_{1,p} h_{p}|}{1-|G_{1}\left( Jz_{p} \right) |}.\] However, this bound is not sharp when \(\gamma_{0}^2(z_p)\) and \(\bar{F}_1(z_p)h_p(z_p)\) have opposite signs. Then we plot the value of \(\gamma_{a,p}\) when \(n=1000\) to illustrate the behavior of different updates. In Fig. 1, we plot the graph of \(\gamma_a\) when CP is BE. As \(J\) increases, the supremum of \(\gamma_a\) also becomes larger. In this case, the benefit of the new update can not be observed since BE is not an accuracy solver. For comparison, in Fig. 2, we plot the graph of \(\gamma_a (z)\) when we choose the exact solver as the CP, i.e., \(R(z)=\text{exp}(-z)\). Different from the case for BE, as \(J\) increases, the supremum of \(\gamma_a\) decreases for both updates. Note that the supremum in the new update is much smaller than that one in the Maday’s update, which implies that our new update is more reasonable. This can be explained through the important gradient in \(\gamma_a\): \(\gamma_0\) defined in [eqn:g_0], \[\begin{align} \gamma_{0} \left( z \right) &=F_{1}\left( z \right) +F_{2}\left( z \right) -\text{exp} \left( -Jz \right);&~\text{(Maday)}\\ \gamma_{0} \left( z \right) &=F_{1}\left( z \right) \text{exp} \left( z \right) +F_{2}\left( z \right) -\text{exp} \left( -Jz \right);&~\text{(New)}. \end{align}\] Obviously, the new update is more reasonable since \(F_1\) and \(F_2\) should not be in the same position.

4.2.2 \(\gamma_{b,p}\)↩︎

The expression of \(\gamma_{b,p}\) is given in 5 .

4.2.3 \(\gamma_{c,p}\gamma_{d,p}\)↩︎

The expression of \(\gamma_{c,p}\gamma_{d,p}\) is given in 7 and 6 .

4.2.4 \(\gamma_{c,p}\gamma_{d,p} \gamma_{e,p}\)↩︎

The expression of \(\gamma_{c,p}\gamma_{d,p} \gamma_{e,p}\) is given in 7 and 6 .