MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

Low-Rank Kronecker-Product Approximation to Multi-Dimensional Nonlocal Operators. Part I. Separable Approximation of Multi-Variate Functions

Wolfgang Hackbusch and Boris N. Khoromskij


The Kronecker tensor-product approximation combined with the $\mathcal{H} $-matrix techniques provides an efficient tool to represent integral operators as well as certain functions $F(A)$ of a discrete elliptic operator $A$ in $\mathbb{R}^{d}$ with a high spatial dimension $d$. In particular, we approximate the functions $A^{-1}$ and $sign(A)$ of a finite difference discretisation $A\in\mathbb{R}^{N\times N}$ with a rather general location of the spectrum. The asymptotic complexity of our data-sparse representations can be estimated by $\mathcal{O}(n^{p}\log^{q}n)$, $p=1,2$, with $q$ independent of $d$, where $n=N^{1/d}$ is the dimension of the discrete problem in one space direction. In this paper (Part I), we discuss several methods of a separable approximation of multi-variate functions. Such approximations provide the base for a tensor-product representation of operators. We discuss the asymptotically optimal sinc quadratures and sinc interpolation methods as well as the best approximations by exponential sums. These tools will be applied in Part II continuing this paper to the problems mentioned above.

Apr 14, 2005
Apr 14, 2005
MSC Codes:
65F50, 65F30, 46B28, 47A80
hierarchical matrices, kronecker tensor-product, sinc interpolation, sinc quadrature, approximation by exponential sums

Related publications

2006 Repository Open Access
Wolfgang Hackbusch and Boris N. Khoromskij

Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. Pt. 1 : Separable approximation of multi-variate functions

In: Computing, 76 (2006) 3/4, pp. 177-202