MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

Construction of data-sparse ${\mathcal H}^2$-matrices by hierarchical compression

Steffen Börm


Hierarchical matrices (${\mathcal H}$-matrices) provide an elegant approach to handling large densely populated matrices: the matrix is split into a hierarchy of blocks, and each block is approximated by a low-rank matrix in factorized form. It has been demonstrated that this representation can be used to treat integral and partial differential equations, solve matrix equations from the field of control theory, and evaluate matrix functions efficiently.

${\mathcal H}^2$-matrices use a refined representation that employs a multi-level structure in order to reduce the storage requirements of hierarchical matrices. It has been shown that ${\mathcal H}^2$-matrices can significantly reduce storage requirements for large problems, in particular when combined with modern error control schemes.

Until now, all algorithms for constructing an efficient approximation of a general matrix by an ${\mathcal H}^2$-matrix required a representation of the entire original matrix to be kept in storage, therefore the storage requirements of ${\mathcal H}^2$-matrix algorithms could be far larger than those of the final approximation. This paper presents a new approach that allows us to construct an ${\mathcal H}^2$-matrix without storing the entire original matrix. The central idea is to approximate submatrices and combine them by an efficient new algorithm to form approximations of larger matrices until the entire matrix has been treated. Using this new approach, many ${\mathcal H}$-matrix algorithms can be "refitted" easily to compute results in the more efficient representation.

Possible applications include efficient matrix arithmetics for the construction of preconditioners, the approximation of matrix functions or solutions of matrix equations, or efficient compression schemes based on the popular cross approximation algorithms.

Sep 24, 2007
Sep 24, 2007
MSC Codes:
65F30, 65D99, 65N38
Hierarchical matrix, H²-matrix, data-sparse

Related publications

2009 Repository Open Access
Steffen Börm

Construction of data-sparse \(\mathscr {H}^2\)-matrices by hierarchical compression

In: SIAM journal on scientific computing, 31 (2009) 3, pp. 1820-1839