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 R^d, 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.