Hierarchical Kronecker tensor-product approximation to a class of nonlocal operators in high dimensions

Wolfgang Hackbusch and Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 13. Apr. 2004 (revised version: July 2004)
Pages: 32
Bibtex
MSC-Numbers: 65F50, 65F30, 46B28, 47A80
Keywords and phrases: hierarchical matrices, kronecker tensor-product, high spatial dimension
Download full preprint: PDF (524 kB), PS ziped (378 kB)

Abstract:
The class of ℋ-matrices allows an approximate matrix arithmetic with almost linear complexity. The combination of the hierarchical and tensor-product format offers the opportunity for efficient data-sparse representations of integral operators and the inverse of elliptic operators in higher dimensions. In the present paper, we apply the ℋ-matrix techniques combined with the Kronecker tensor-product approximation to represent integral operators as well as certain functions ℱ(A) of a discrete elliptic operator A in a hypercube ^d ∈ ℝ^d in the case of a high spatial dimension d. In particular, we approximate the functions A⁻¹ and sign(A) of a finite difference discretisations A ∈ ℝ^N×N with rather general location of the spectrum. The asymptotic complexity of our data-sparse representations can be estimated by 𝒪(n^p log ^qn), p = 1,2, with q independent of d, where n = N^1∕d is the dimension of the discrete problem in one space direction.