On H^2-Matrices

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

Contact the author: Please use for correspondence this email.
Submission date: 16. Jul. 1999
Pages: 18
published 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 / H.-J. Bungartz ... (eds.)
Berlin [u. a.] : Springer, 2000. - P. 9 - 29 
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50, 65N38, 68P05, 45B05, 35C20
Keywords and phrases: hierarchical matrices, hierarchical bases, full matrices, fast matrix-vector multiplication, bem, fem
Download full preprint: PDF (433 kB), PS ziped (192 kB)

Abstract:
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 log^a 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.