Data-sparse approximation by adaptive -Matrices

Wolfgang Hackbusch and Steffen Börm

Contact the author: Please use for correspondence this email.
Submission date: 15. Nov. 2001
Pages: 36
published in: Computing, 69 (2002) 1, p. 1-35 
DOI number (of the published article): 10.1007/s00607-002-1450-4
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50, 65N38, 68P05, 45B05, 35C20
Keywords and phrases: hierarchical matrices, nested bases, full matrices, fast matrix-vector multiplication, bem, fem
Download full preprint: PDF (565 kB), PS ziped (257 kB)

Abstract:
A class of matrices (H²-matrices) has recently been introduced for storing discretisations of elliptic problems and integral operators from the BEM.

These matrices have the following properties:

1. They are sparse in the sense that only few data are needed for their representation.
2. The matrix-vector multiplication is of linear complexity.
3. In general, sums and products of these matrices are no longer in the same set, but after truncation to the H²-matrix format these operations are again of quasi-linear complexity.

We introduce the basic ideas of H- and H²-matrices and present an algorithm that adaptively computes approximations of general matrices in the latter format.