MiS Preprint Repository

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)$.