MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV ( that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint

On H^2-Matrices

Wolfgang Hackbusch, Boris N. Khoromskij and Stefan A. Sauter


A class of matrices (H-matrices) has recently been introduced by one of the authors. These matrices have the following properties: (i) They are sparse in the sense that only few data are needed for their representation. (ii) The matrix-vector multiplication is of almost linear complexity. (iii) In general, sums and products of these matrices are no longer in the same set, but their truncations to the H-matrix format are again of almost linear complexity. (iv) The same statement holds for the inverse of an H-matrix. The term "almost linear complexity" used above means that estimates are given by O(n loga n): The logarithmic factor can be avoided by a further improvement, which is described in the present paper. We prove that the storage requirements and the cost of the matrix-vector multiplication is strictly linear in the dimension n; while still (full) system matrices of the boundary element method can be approximated up to the discretisation error.

MSC Codes:
65F05, 65F30, 65F50, 65N38, 68P05, 45B05, 35C20
hierarchical matrices, hierarchical bases, full matrices, fast matrix-vector multiplication, bem, fem

Related publications

2000 Repository Open Access
Wolfgang Hackbusch, Boris N. Khoromskij and Stefan A. Sauter

On \(\mathscr {H}^2\)-matrices

In: Lectures on applied mathematics : proceedings of the symposium organized by the Sonderforschungsbereich 438 on the occasion of Karl-Heinz Hoffmann's 60th birthday, Munich, June 30 - July 1, 1999 / Hans-Joachim Bungartz... (eds.)
Berlin [u. a.] : Springer, 2000. - pp. 9-29