# Compression Challenges in Large Scale Partial Differential Equation Solvers
## 4 Communication in Distributed Systems
### Inexact Parallel-in-Time Integrators  
An example of communication in distributed systems is the propagation of initial values in parallel-in-time integrators for initial value problems \(\dot{u}=f(u)\), \(u(t_{0})=a\), in particular of hybrid parareal type [63]. Here, the initial value problem is interpreted as large equation system  
\[F(U)= \begin{bmatrix}a&-u^{0}(t_{0})&&\\ \dot{u}^{0}-f(u^{0})&&\\ &u^{0}(t^{1})&-u^{1}(t^{1})&\\ &&\dot{u}^{1}-f(u^{1})&\\ &&u_{1}(t^{2})&-u^{2}(t^{2})\\ &&\ddots&\end{bmatrix} =0 \tag{3}\]  
for a set \(U=(u^{0},\ldots,u^{N})\) of subtrajectories \(u^{n}\in C^{1}([t^{n},t^{n+1}])\) on a time grid \(t^{0},t^{1},\ldots,t^{N+1}\). Instead of the inherently sequential triangular solve, i.e., time stepping, the system is solved by a stationary iterative method with an approximate solver \(S\):  
\[U_{j+1}=U_{j}+S(F(U_{j})). \tag{4}\]  
The advantage is that a large part of the approximate solver \(S\) can be parallelized, by letting \(S^{-1}=\mathcal{F}^{-1}+\mathcal{G}^{-1}\), where \(\mathcal{G}\) is an approximation of the derivative \(-F^{\prime}\) on a spatial and/or temporal coarse grid and provides the global transport of information, while \(\mathcal{F}\) is a block-diagonal approximation of \(-F^{\prime}\) on the fine grid and cares for the local reduction of fine grid residuals. The bulk of the work is done in applying the fine grid operator \(\mathcal{F}^{-1}\), where all blocks can be treated in parallel. Only the coarse grid solution operator \(\mathcal{G}^{-1}\) needs to be applied sequentially. If the parallelized application of \(S\) is significantly faster than computing a single subtrajectory up to fine grid discretization accuracy, reasonable parallel efficiencies above 0.5 can be achieved [64]. For a fast convergence, however, the terminal values \(u^{n}(t^{n+1})\) have to be propagated sequentially as initial values of \(u^{n+1}(t^{n+1})\) over all subintervals during each application of the approximate solver \(S\). Thus, communication time can significantly affect the overall solution time [65]. Compressed communication can therefore improve the time per iteration, but may also impede on the convergence speed and increase the number of iterations. A judicious choice of compression factor and distortion must rely on error estimates and run time models. The worst-case error analysis presented in [65] provides a bound of the type  
\[\|U_{j}-U_{*}\|\leq c_{j}^{n}\ \left(\frac{1+\Delta_{C}}{1-\Delta_{C}/\rho} \right)^{n+2}, \tag{5}\]  
depending on the relative compression error \(\Delta_{C}\), the local contraction rate \(\rho\) of \(S\), and factors \(c_{j}^{n}\) independent of communication. This can be used to compute an upper bound on the number \(J(\Delta_{C})\) of iterations in dependence of the compression error. The run time of the whole computation is \(T_{\text{par}}=N(t_{G}+t_{C}(\Delta_{C}))+J(\Delta_{C})(t_{G}+t_{F})\), where \(t_{G}\) is the time required for the sequential part of \(S\), \(t_{F}\) for the parallel part, and the function \(t_{C}\) is the communication time depending on the compression error, including compression time. Minimizing \(T_{\text{par}}\) can be used to optimize for \(\Delta_{C}\), as long as the relation between \(\Delta_{C}\) and \(t_{C}\) is known. For finite element coefficients, most schemes will lead to \(t_{C}\approx-c\log\Delta_{C}\), i.e., a communication time proportional to the bits spent per coefficient, with the proportionality factor \(c\) depending on bandwidth, problem size, and efficiency of the compressor. Variation of different parameters in this model around a nominal scenario of contemporary compute clusters as shown in Figure 3 suggest that in many current HPC situations, the expected benefit for the run time is small. The predicted run time improvement for the nominal scenario is about 5%, and does not vary much with, for example, the requested final accuracy (Figure 3, right).