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 (www.arxiv.org) 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
66/1999
A sparse ${\cal H}$-matrix arithmetic: general complexity estimates
Wolfgang Hackbusch and Boris N. Khoromskij
Abstract
In a preceding paper ([1]), a class of matrices (${\cal H}$-matrices) has been introduced which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. Several types of ${\cal H}$-matrices have been analysed in ([1], [2]) which are able to approximate integral (nonlocal) operators in FEM and BEM applications in the case of quasi-uniform unstructured meshes. In the present paper, the general construction of ${\cal H}$-matrices on rectangular and triangular meshes is proposed and analysed. First, the reliability of ${\cal H}$-matrices in BEM is discussed. Then, we prove the optimal complexity of storage and matrix-vector multiplication in the case of rather arbitrary admissibility parameters $\eta < 1$ and for finite elements up to the order 1 defined on quasi-uniform rectangular/triangular meshes in Rd, d=1,2,3. The almost linear complexity of the matrix addition, multiplication and inversion of ${\cal H}$-matrices is also verified. [1] W. Hackbusch: A sparse matrix arithmetic based on ${\cal H}$-matrices. Part I: Introduction to ${\cal H}$-matrices. Computing 62 (1999), 89-108. [2] W. Hackbusch and B. N. Khoromskij: A sparse ${\cal H}$-matrix arithmetic. Part II. Application to multi-dimensional problems. (published in the MPI MIS Preprint series, No. 22/1999, Leipzig, 1999. To appear in Computing.
