## 7 Algorithms for HPC Systems in the Exascale Era
### Parallel Solvers for Exascale Computing
#### 7.2.1 \"Implicit-Explicit\" and \"Parallel in Time\"
For this purpose, consider \(\Theta_{N}\) as the set made up of the \(N+1\) equally spaced points \(\left\{t_{n}\right\}_{n=0,\ldots,N}\) where \(t_{n}=t_{0}+\Delta*n,n=1,\ldots,\ N\) and where \(\Delta=\frac{T}{N}\)._  
_Let a time block (or simply block) denote the discretization of a time subinterval \([t_{n},t_{n+1}]\) using \(M>0\) grid points,_  
\[E(h):=\|u-u_{h}\|\leq Ch^{p} \tag{182}\]2  
_where \(\tau_{m}\in[0,1]\) denotes normalized grid points in time used for all \(N\) time subintervals._  
_Let a block variable be a vector_  
\[E(h):=\|u-u_{h}\|\leq Ch^{p} \tag{182}\]3  
_where \(u_{n,m}\) is an approximation of \(u(\tau_{n,m})\) on the time block for the time subinterval \([t_{n},t_{n+1}]\)._  
_Finally, let us denote as block operators the two functions \(\phi:\Re^{M}\to\Re^{M}\) and \(\chi:\Re^{M}\to\Re^{M}\) for which the block variables of a numerical solution of (189) satisfy_  
\[E(h):=\|u-u_{h}\|\leq Ch^{p} \tag{182}\]4 \[E(h):=\|u-u_{h}\|\leq Ch^{p} \tag{182}\]5  
_where \(\mathbf{1}=[1,\ldots,1]^{T}\), where the time integration operator \(\phi\) is bijective and where \(\chi\) is a transmission operator. The time propagator \(\psi\) updating \(\mathbf{u}_{n}\) to \(\mathbf{u}_{n+1}\) is given by_  
\[E(h):=\|u-u_{h}\|\leq Ch^{p} \tag{182}\]6_The numerical approximation (190) of (189) can be described as the following all-at-once global problem_  
\[\left( \begin{array}{ccc}\phi\\ -\chi&\phi\\ &\ddots&\ddots\\ &&-\chi&\phi\end{array} \right)\left[ \begin{array}{c}\mathbf{u}_{1}\\ \mathbf{u}_{2}\\ \vdots\\ \mathbf{u}_{N}\end{array} \right]=\left[ \begin{array}{c}\chi(u_{0}\mathbf{1})\\ \mathbf{0}\\ \vdots\\ \mathbf{0}\end{array} \right] \tag{191}\]  
_Iterative Pint algorithms solve (191) by updating a vector \(\mathbf{u}^{k}=\left[u_{1}^{k},\ldots,u_{N}^{k}\right]^{T}\) to \(\mathbf{u}^{k+1}\) until some stopping criterion is satisfied. If the global iteration can be written as a local update for each block variable separately, the local update formula is called a block iteration._  
_Let a primary block iteration be an updating formula of the form_  
\[\mathbf{u}_{n+1}^{k+1}=\mathbf{\mathrm{B}}_{1}^{0}\Big{(}\mathbf{u}_{n+1}^{k}\Big{)}+\mathbf{ \mathrm{B}}_{0}^{1}\Big{(}\mathbf{u}_{n}^{k+1}\Big{)}+\mathbf{\mathrm{B}}_{0}^{0} \Big{(}\mathbf{u}_{n}^{k}\Big{)},\ \mathbf{u}_{0}^{k}=u_{0}\mathbf{1},\ \forall k\in\mathbb{N}, \tag{192}\]  
_where \(n\geq 0\), and where \(\mathbf{\mathrm{B}}_{1}^{0}\), \(\mathbf{\mathrm{B}}_{0}^{1}\), \(\mathbf{\mathrm{B}}_{0}^{0}\) are operators that satisfy the consistency condition_  
\[\Big{(}\mathbf{\mathrm{B}}_{1}^{0}-\mathbf{I}\Big{)}\psi+\mathbf{\mathrm{B}}_{0}^{1}+\mathbf{ \mathrm{B}}_{0}^{0}=0. \tag{193}\]  
_The solution of the all-at-once global problem (191) by an iterative method based on a primary block iteration of the type (192) represents the Parallel-In-Time approach for the solution of time-dependent ODE (189)._  
In Table 9, a summary of the the most popular Pint methods, and their block iteration operators, are reported (see Gander et al. [173] for details). Algorithm 10 describes an implementation of the P_Int_ approach. We observe that Algorithm 10 lends itself well to parallelization: indeed, if we imagine dividing the \(N\) vectors \(\mathbf{u}_{n}\) among \(P\) concurrent tasks, then  
* The initial approximation vectors \(\mathbf{u}_{n}^{0}\) (see lines 5-7 of Algorithm 10) can be computed concurrently and independently of each other in an _\"embarrassingly parallel\"_ approach (no communications are needed among tasks);
* The initial vectors \(\mathbf{u}_{0}^{k}\) (see lines 8-10 of Algorithm 10) can be computed by all the \(P\) tasks concurrently and independently of each other;
* In each iteration of the iterative method that is needed to refine the approximation of the vectors \(\mathbf{u}_{n}\) (see lines 11-17 of Algorithm 10), the computation of vectors \(\mathbf{z}_{n}^{k}\) can be performed concurrently and locally to the assigned task \(p\).