A sparse -Matrix Arithmetic, Part II: Application to Multi-Dimensional Problems

Wolfgang Hackbusch and Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 23. Mar. 1999
Pages: 20
published in: Computing, 64 (2000) 1, p. 21-47 
DOI number (of the published article): 10.1007/s006070050002
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50
Keywords and phrases: fast algorithms, hierarchical matrices, hierarchical block partioning, sparse matrices, matrix inversion, bem, fem
Download full preprint: PDF (534 kB), PS ziped (222 kB)

Abstract:
The preceding Part I of this paper has introduced a class of matrices (-matrices) which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. The matrices discussed in Part I are able to approximate discrete integral operators in the case of one spatial dimension.

In the present Part II, the construction of -matrices is explained for FEM and BEM applications in two and three spatial dimensions. The orders of complexity of the various matrix operations are exactly the same as in Part I. In particular, it is shown that the applicability of -matrices does not require a regular mesh. We discuss quasi-uniform unstructured meshes and the case of composed surfaces as well.