-matrix approximation on graded meshes

Wolfgang Hackbusch and Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 29. Aug. 1999
Pages: 11
published in: The mathematics of finite elements and applications X, MAFELAP 1999 : proceedings of the 10th conference, Brunel Univ., Uxbridge, Middlesex, GB, June 22-25, 1999 / J. R. Whiteman (ed.)
Amsterdam [u. a.] : Elsevier, 2000. - P. 307 - 316 
Bibtex
Keywords and phrases: fast algorithms, hierarchical matrices, data-sparse matrices, mesh refinement, bem, fem
Download full preprint: PDF (441 kB), PS ziped (197 kB)

Abstract:
In a preceding paper, 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 were analysed 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 special class of -matrices on graded meshes is analysed. We investigate two types of separation criteria for the construction of the cluster tree which allow to optimise either the approximation power (cardinality-balancing strategy) or the complexity (distance-balancing strategy) of the -matrices under consideration. For both approaches, we prove the optimal complexity and approximation results in the case of composite meshes and tensor-product meshes with polynomial/exponential grading in R^d, d=1,2,3.