# Compression Challenges in Large Scale Partial Differential Equation Solvers
## 3 In-Memory Compression
### Scalar Quantization for Overlapping Schwarz Smoothers  
One particularly simple method of data compression is a simple truncation of mantissa and exponent bits, i.e., using IEEE 754 single precision (4 bytes) instead of double precision (8 bytes) representations [55], or even the half precision format (2 bytes) popularized by recent machine learning applications. Conversion between the different formats is done in hardware on current CPUs and integrated into load/store operations, such that the compression overhead is minimal. Consequently, using mixed precision arithmetics has been considered for a long time, in particular in dense linear algebra [56] and iterative solvers [57; 58]. Depending on the algorithm's position in the roofline model, either the reduced memory traffic (Basic Linear Algebra Subroutines (BLAS) level 1/2, vector-vector and matrix-vector operations) or the faster execution of lower precision floating point operations (BLAS level 3, matrix-matrix operations) is made use of. An important building block of solvers for elliptic PDEs of the type  
\[-\text{div}(\sigma\
abla u) =f \text{in }\Omega\] \[n^{T}\sigma\
abla u+\alpha u =\beta \text{on }\partial\Omega\]  
is the iterative solution of the sparse, positive definite, and ill-conditioned linear equation systems \(Ax=b\) arising from finite element discretizations. For this task, usually preconditioned conjugate gradient (CG) methods are employed, often combining a multilevel preconditioner with a Jacobi smoother [2]. For higher order finite elements, with polynomial ansatz order \(p>2\), the effectivity of the Jacobi smoother quickly decreases, leading to slow convergence. Then it needs to be replaced by an overlapping block Jacobi smoother \(B\), with the blocks consisting of all degrees of freedom associated with cells around a grid vertex. Application of this smoother then involves a large number of essentially dense matrix-vector multiplications of moderate size:  
\[B^{-1}=\sum_{\xi\in\mathcal{N}}P_{\xi}A_{\xi}^{-1}P_{\xi}^{T}. \tag{1}\]  
Here, \(\mathcal{N}\) is the set of grid vertices, \(A_{\xi}\) is the symmetric submatrix of \(A\) corresponding to the vertex \(\xi\), and \(P_{\xi}\) distributes the subvector entries into the global vector. Application of this smoother dominates the solver run time, and is strictly memory bound due to the large number of dense matrix-vector multiplications. Compressed storage of \(A_{\xi}^{-1}\) as \(\bar{A}_{\xi}^{-1}\) using low precision representation of its entries has been investigated in [38]. A detailed analysis reveals that the impact on the preconditioner effectivity and hence the CG convergence is determined by \(\|A^{-1}-\bar{A}^{-1}\|_{2}\). This suggests that a uniform quantization of submatrix entries should be preferable in view of rate-distortion optimization. Accordingly, fixed point representations have been considered as an alternative to low precision floating point representations. Moreover, the matrix entries exhibit a certain degree of correlation, which can be exploited by dividing \(A_{\xi}^{-1}\) into square blocks to be stored independently. A uniform quantization of their entries \(c\) within the block entries' range \([c_{\min},c_{\max}]\) as \(l=q(c)\) and corresponding dequantizing \(\tilde{c}=q^{+}(l)\) is given by  
\[q(c)= \begin{cases}\frac{c-c_{\min}}{\Delta}\,\rfloor,&c<c_{\max}\\ 2^{k}-1,&c=c_{\max},\end{cases} \qquad q^{+}(l)=c_{\min}+\Delta\Big{(}l+\frac{1 }{2}\Big{)}, \tag{2}\]  
with step size \(\Delta=2^{-k}(c_{\max}-c_{\min})\), providing minimal entry-wise quantization error \(\Delta/2\) for the given bit budget. Decompression can then be performed inline during application of the preconditioner, i.e., during the matrix-vector products.