Construction and Arithmetics of -Matrices

Lars Grasedyck and Wolfgang Hackbusch

Contact the author: Please use for correspondence this email.
Submission date: 28. Nov. 2002 (revised version: July 2004)
Pages: 32
published in: Computing, 70 (2003) 4, p. 295-334 
DOI number (of the published article): 10.1007/s00607-003-0019-1
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50
Keywords and phrases: hierarchical matrices, data-sparse approximations, fast solvers, formatted matrix operations
Download full preprint: PDF (680 kB), PS ziped (659 kB)

Abstract:
In previous papers a class of H-matrices was introduced which are data-sparse and allow an approximate matrix arithmetic of nearly optimal complexity. In this paper we analyse the complexity (storage, addition, multiplication and inversion) of the H-matrix arithmetics. Two criteria, the sparsity and idempotency, are sufficient to give the desired bounds. For standard finite element and boundary element applications we present a construction of an H-matrix format for which we can give explicit bounds for the sparsity and idempotency.