

Preprint 66/1999
A sparse
-matrix arithmetic: general complexity estimates
Wolfgang Hackbusch and Boris N. Khoromskij
Contact the author: Please use for correspondence this email.
Submission date: 26. Nov. 1999
Pages: 20
published in: Journal of computational and applied mathematics, 125 (2000) 1-2, p. 479-501
DOI number (of the published article): 10.1016/S0377-0427(00)00486-6
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50
Keywords and phrases: hierarchical matrices, data-sparse approximations, formatted matrix operations, fast solvers, bem, fem
Download full preprint: PDF (542 kB), PS ziped (226 kB)
Abstract:
In a preceding paper ([1]), a class of matrices (-matrices) has been introduced which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. Several types of
-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 -matrices on rectangular and triangular meshes is proposed and analysed. First, the reliability of
-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
< 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
-matrices is also verified.
[1] W. Hackbusch: A sparse matrix arithmetic based on -matrices. Part I: Introduction to
-matrices. Computing 62 (1999), 89-108.
[2] W. Hackbusch and B. N. Khoromskij: A sparse -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.