Abstract
In this chapter, the authors present hierarchical matrices, which are a powerful numerical tool that allows reducing to a logarithmic order both the storage needs and computational time in exchange for a controlled accuracy loss, thanks to the compression of part of the original data to form low-rank blocks. This type of matrices presents certain particularities due to the storage layout, the different blocks configurations, and a hierarchically and nested partitioned structure of blocks; the presence of dense and low-rank blocks of various dimensions; and the recursive nature of the algorithms that compute the h-algebra operations. Thanks to the programming model OmpSs-2 and specifically to two novel features it incorporates, a fair parallel efficiency based on task-parallelism can be achieved in shared memory environments.
TopLinear Algebra Background On Hierarchical Matrices
From a mathematical perspective, hierarchical matrices are included in the set of compressed structures (Cheng et al., 2003). This is because they are built employing procedures that remove the “less representative” entries (which is understood as compression) until a pre-established ratio between accuracy loss and future computations acceleration is achieved. Conceptually, the compressed structures lay between dense and sparse linear algebra elements, as there is a presence of null elements in them, but not that high to consider them sparse matrices.
Now the authors present some mathematical definitions that are necessary for understanding the foundations of H-Matrices (Grasedyck et al., 2003) (Hackbusch et al., 2004) (Hackbusch, 2015). The first terms that need to be presented are the ones employed in the process of determining the “importance” of a certain matrix entry with respect to the others: eigenvalues, eigenvectors and singular values.
Definition 7.1. (Eigenvalues and eigenvectors) Let 
, then if there exists a nonzero vector 𝜐∈Rn, and a nonzero scalar 𝜆∈R such that A𝜐=𝜆𝜐 has a nontrivial solution, then 𝜐 is an eigenvector of A, and 𝜆 is an eigenvalue of A.
Definition 7.2. (Singular values) Let 
, then let 𝜆1,𝜆2…𝜆∈R be the eigenvalues of ATA (with repetitions). Order them in such a way that 𝜆1≥𝜆2≥…𝜆n≥0 and let 𝜎i=√𝜆i, so that 𝜎1≥𝜎2≥…𝜎n≥0. Then the scalars 𝜎i∈R are the singular values of A.
With these two definitions in mind, prior to understanding how the compression of data is performed in H-Matrices and similar structures, two propositions regarding the singular values importance and sense need to be presented.
Proposition 7.1. The number of nonzero singular values of A equals the rank of A.
Proposition 7.2. Let 
. Then the maximum value of kAxK, where x ranges over unit vectors in Rn, is the largest singular value 𝜎1, and this is achieved when x is an eigenvector of ATA with eigenvalue (𝜎1)2.
Key Terms in this Chapter
OmpSs-2: Parallel Programming Model designed, developed, and maintained by the Barcelona Supercomputing Center which provides novelty features for task-parallelism in shared memory environments.
H2Lib: Linear Algebra library designed, developed, and maintained by the Christian-Albrechts-Universität zu Kiel that incorporates all the needed algebra and algorithms to build and operate with hierarchical matrices.
TDG: Task Dependency Graph. This is the name associated with the graph generated to represent the dependencies between the different tasks in a task-parallel execution.
LU Factorization: Operation that decomposes a given matrix into the product of two triangular matrices, the left one being unit lower triangular (L) and the right one upper triangular (U).
H-Matrix: Hierarchical matrix. A powerful numerical tool that allows to compress the information in such a way that part of the data is stored in a low-rank format, saving storage and computational costs in exchange for a controlled accuracy loss.