## 7 Algorithms for HPC Systems in the Exascale Era
### Parallel Solvers for Exascale Computing
#### 7.2.3 Parallel Iterative and Direct Linear Solver
Definition 6: Definition of \"block cluster quad-tree\" of a matrix \(A\)  
Let \(\mathcal{T}_{I}(L)\) be a binary tree [190] with the \(L+1\) levels \(l=0,\ldots,L\) and denote by \(T_{I}\) the set of its nodes. \(\mathcal{T}_{I}\) is called a binary cluster tree corresponding to an index set \(1\) if the following conditions hold:  
1. Each node of \(T_{I}\) is a subset of the index set \(I\);
2. I is the root of \(\mathcal{T}_{I}(L)\) (i.e., the node at the \(0\)-th level of \(\mathcal{T}_{I}(L)\));
3. If \(\tau\in T_{I}\) is a leaf (i.e, a node at the \(L\)-th level of \(\mathcal{T}_{I}(L)\)), then \(|\tau|\leq C_{leaf}\);
4. If \(\tau\in T_{I}\) is not a leaf whose set of sons is represented by \(S(\tau)\subseteq T_{I}\), then \(|S(\tau)|=2\) and \(\tau=\bigcup_{\tau^{\prime}\in S(\tau)}\tau^{\prime}\)  
Let \(I\) be an index and let \(AC(\tau\times\sigma)=0,1\) a logical value representing an \"Admissibility Condition\" on \(\tau\times\sigma\). Moreover, let \(\mathcal{T}_{I}(L)\) be a binary cluster tree on the index set \(I\). The block cluster quad-tree \(\mathcal{T}_{I\times I}\) corresponding to \(\mathcal{T}_{I}(L)\) and to the admissibility condition \(AC(\tau\times\sigma)\) could be built by the procedure represented in Algorithm 13. ```
1:procedureBlockClusterQuadTree(\(\mathcal{T}_{I\times I}(L)\), \(L\), \(AC(\tau\times\sigma)\), \(\tau\times\sigma\))
2:Input:\(\mathcal{T}_{I\times I}(L)\), \(AC(\tau\times\sigma)\), \(L\), \(l\), \(\tau\times\sigma\)
3:if(\(AC(\tau\times\sigma)=0\)and\(l<L\))then
4:\(S(\tau\times\sigma)=\{\tau^{\prime}\times\sigma^{\prime}:\tau^{\prime}\in S(\tau)\), \(\sigma^{\prime}\in S(\sigma)\}\)
5:for\(\tau^{\prime}\times\sigma^{\prime}\in S(\tau\times\sigma)\)do
6:BlockClusterQuadTree(\(\mathcal{T}_{I\times I}(L)\), \(L,l+1\), \(AC(\tau^{\prime}\times\sigma^{\prime})\), \(\tau^{\prime}\times\sigma^{\prime}\))
7:endfor
8:else
9:\(S(\tau\times\sigma)=\emptyset\)
10:endif
11:endprocedure
```  
**Algorithm 13** Procedure for building the block quad-tree \(\mathcal{T}_{I\times I}(L)\) corresponding to a cluster tree \(\mathcal{T}_{I}(L)\) and an admissibility condition \(AC\). The index set \(\tau\times\sigma\) and the value \(l\) to be used in the first call to the recursive BlockClusterQuadTree procedure are such that \(\tau=\sigma=I,l=0\). ```
1:procedureBlockClusterQuadTree(\(\mathcal{T}_{I\times I}(L)\), \(L\), \(AC(\tau\times\sigma)\), \(\tau\times\sigma\))
2:Input:\(\mathcal{T}_{I\times I}(L)\), \(AC(\tau\times\sigma)\), \(L\), \(l\), \(\tau\times\sigma\)
3:if(\(AC(\tau\times\sigma)=0\)and\(l<L\))then
4:\(S(\tau\times\sigma)=\{\tau^{\prime}\times\sigma^{\prime}:\tau^{\prime}\in S(\tau)\), \(\sigma^{\prime}\in S(\sigma)\}\)
5:for\(\tau^{\prime}\times\sigma^{\prime}\in S(\tau\times\sigma)\)do
6:BlockClusterQuadTree(\(\mathcal{T}_{I\times I}(L)\), \(L,l+1\), \(AC(\tau^{\prime}\times\sigma^{\prime})\), \(\tau^{\prime}\times\sigma^{\prime}\))
7:endfor
8:else
9:\(S(\tau\times\sigma)=\emptyset\)
10:endif
11:endprocedure
```  
**Algorithm 14** Procedure for building the block quad-tree \(\mathcal{T}_{I\times I}(L)\) corresponding to a cluster tree \(\mathcal{T}_{I}(L)\) and an admissibility condition \(AC\). The index set \(\tau\times\sigma\) and the value \(l\) to be used in the first call to the recursive BlockClusterQuadTree procedure are such that \(\tau=\sigma=I,l=0\). Definition 7: Definition of \(\mathcal{H}\)-matrix  
Let \(A\in\Re^{N\times N}=\left(a_{i,j}\right)_{i,j=1,\ldots,N}\) be a matrix, let \(I=\{1,\ldots,N\}\) the index set of \(A\), and let \(k\in\mathcal{N}\). Let us assume that, for a vector \(v\) and a subset \(\tau\subset I\), \(v_{|\tau}\) represents the restriction vector \(\left(v_{j}\right)_{j\in\tau}\) of \(v\) to \(\tau\), and that, for a matrix \(A\) and subsets \(\tau,\sigma\subset I\), the notation \(A_{|\tau\times\sigma}\) represents the block \(\big{(}A_{ij}\big{)}_{i\in\tau,j\in\mathcal{C}}\).