MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV ( that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint

Towards $\mathcal{H}$-matrix approximation of linear complexity

Wolfgang Hackbusch and Boris N. Khoromskij


In preceding papers, the authors have analysed a class of matrices (${\cal H}$-matrices) which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. Several types of ${\cal H}$-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 ${\cal H}$-matrices with improved data sparsity to approximate elliptic problems posed in $\mathcal{R}^d$, d=1,2,3. For the evaluation of integral operators on spatial domains in $\mathcal{R}^d$, 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 $O(log^dn)$ down to $O(log^{d-1}n)$.

MSC Codes:
65F50, 65F30, 65F05, 65R20, 15A09
hierarchical matrices, matrix compression, wire-basket h-matrix approximation, bem

Related publications

2001 Repository Open Access
Wolfgang Hackbusch and Boris N. Khoromskij

Towards \( \mathscr{H} \)-matrix approximation of linear complexity

In: Problems and methods in mathematical physics : the Siegfried Prössdorf memorial volume ; proceedings of the 11th TMP, Chemnitz, Germany, March 25 - 28, 1999 / Johannes Elschner... (eds.)
Basel [u. a.] : Birkhäuser, 2001. - pp. 194-220
(Operator theory : advances and applications ; 121)