MiS Preprint Repository

In a preceding paper ([1]), a class of matrices ($\mathcal{H}$-matrices) has been introduced which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. Several types of $\mathcal{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 $\mathcal{H}$-matrices on rectangular and triangular meshes is proposed and analysed. First, the reliability of $\mathcal{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 R^d, d=1,2,3. The almost linear complexity of the matrix addition, multiplication and inversion of $\mathcal{H}$-matrices is also verified.
[1] W. Hackbusch: A sparse matrix arithmetic based on $\mathcal{H}$-matrices. Part I: Introduction to $\mathcal{H}$-matrices. Computing 62 (1999), 89-108.
[2] W. Hackbusch and B. N. Khoromskij: A sparse $\mathcal{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.