## 7 Algorithms for HPC Systems in the Exascale Era
### Parallel Solvers for Exascale Computing
#### 7.2.3 Parallel Iterative and Direct Linear Solver  
A sparse linear system solution is sometimes the most computationally demanding step in large-scale research and engineering simulations. Even though iterative approaches are increasingly being used to tackle many of these issues, direct solvers are still frequently used and will remain essential at the Exascale [156; 179; 180]. The fundamental advantage of direct solutions is their robustness. In fact, when solving extremely ill-conditioned linear systems, direct solvers are often the method of choice, that is, once the system matrix has been rearranged. When compared to iterative methods, where the complexity is related to the primary kernel in an iteration (which is typically a matrix-vector multiplication, the cost of which is typically proportionate to the number of nonzeros in the matrix) and the number of iterations required for convergence, the main drawbacks of direct approaches are their computational expense and memory usage [156]. Exascale computing will continue to require multilevel techniques because of their high concurrency properties. Some multi-level techniques exhibit a \"_natural resilience to faults_\" [156], which may serve as a useful foundation for the development of fault-tolerant algorithms. While multilevel approaches offer many advantageous characteristics, the applicability of any one algorithm is usually very limited. Exascale computing does, in fact, constrain algorithmic selections of multilevel approaches, conditioning selections for relaxation operators and the Multigrid schema structure (e.g., W-cycles ought to be disregarded due to their substantial communications costs) [156]. In recent years, the effort spent by some scientific communities around the world (for example, see the USA Exascale Computung Project (ECP) Multiprecision Effort Team [181]) has obtained great results in developing and deploying new mixed-precision technology. Some of the most promising and impactful achievements concern:  
* Mixed-precision dense and sparse LU factorization based on Iterative Refinement (IR);
* Mixed-Precision GMRES based on IR;
* Compressed-Basis (CB) GMRES. One of the most crucial extreme scale needs is the relaxation and lowering of synchronization, which may also help to relieve load balancing pressure. It is probably difficult to completely eliminate periodic synchronization in solvers, although many algorithms could be designed in a way that requires a lot less synchronization. Within the category of standard iterative methods, examples of such a type of algorithm are the \"_-step_\" CA-GMRES iterative method [21; 182], which uses a redesign of the KSM algorithms based on BLAS 2 and 3 operations (products of a vector by a matrix, matrices products, etc. ), which have a higher computational granularity (i.e., a higher ratio of computation time to communication time) than the original KSM formulation based on BLAS 1 operations. system of \(N\) particles. During its history [185; 186; 187], FFM was the basis for other useful applications such as the fast multiplication of vectors with fully populated special matrices. In the context of linear algebra, FFM takes the name of fast multiplication by \"\(\mathcal{H}\)_-matrices_\" which are a combination of the \"_Panel Clustering Method_\", and the \"_mosaic skeleton matrices_\" approaches [188; 189]. According to [188; 189], let us introduce \"_Hierarchical\" matrices_ (also called \(\mathcal{H}\)-matrices). First of all, it is necessary to introduce the concepts of the R\(k\)-matrix and the \"_block cluster quad-tree_\". Definition 5: Definition of R\(k\)-matrix  
Let \(R\in\Re^{M\times N}\) be a matrix of the form  
\[R=AB^{T},\ A\in\Re^{M\times k},\ B\in\Re^{k\times N}.\]  
Then, \(R\) is called an \(\mathbf{R}k\)-matrix. Any matrix of a rank of at most \(k\) can be represented as an R\(k\)-matrix, and each \(\mathbf{R}k\)-matrix has at most a rank of \(k\).