Towards -matrix approximation of linear complexity

Wolfgang Hackbusch and Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 07. Mar. 2000
Pages: 23
published in: Problems and methods in mathematical physics : the Siegfried Prössdorf memorial volume ; proceedings of the 11th TMP, Chemnitz, Germany, March 25 - 28, 1999 / J. Elschner ... (eds.)
Basel [u. a.] : Birkhäuser, 2001. - P. 194 - 220
(Operator theory : advances and applications ; 121) 
Bibtex
MSC-Numbers: 65F50, 65F30, 65F05, 65R20, 15A09
Keywords and phrases: hierarchical matrices, matrix compression, wire-basket h-matrix approximation, bem
Download full preprint: PDF (513 kB), PS ziped (216 kB)

Abstract:
In preceding papers, the authors have analysed a class of matrices (-matrices) which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. Several types of -matrices were shown to provide good approximation of nonlocal (integral) operators in FEM and BEM applications.

In the present paper, we develop special classes of -matrices with improved data sparsity to approximate elliptic problems posed in , d=1,2,3. For the evaluation of integral operators on spatial domains in , the idea is to apply degenerate kernel expansions supported only on the boundaries of the geometrical clusters. This results in an algorithm of linear storage expenses, O(n), which includes one call for an optimal Dirichlet solver (e.g., multi-grid method) on the involved cluster. In the case of a tensor product finite element ansatz space, we propose improved degenerate expansions of the kernel based on a separation with respect to the full set of one-dimensional variables..

For BEM applications applied to rather general elliptic operators, our approach reduces the order of expansion from down to .