

Preprint 36/2008
Fast and Accurate Tensor Approximation of Multivariate Convolution with Linear Scaling in Dimension
Boris N. Khoromskij
Contact the author: Please use for correspondence this email.
Submission date: 22. Apr. 2008 (revised version: May 2009)
Pages: 28
published in: Journal of computational and applied mathematics, 234 (2010) 11, Special Issue, p. 3122-3139
DOI number (of the published article): 10.1016/j.cam.2010.02.004
Bibtex
MSC-Numbers: 65F30, 65F50, 65F35
Keywords and phrases: multi-dimensional convolution, Tucker decomposition, composite grids, Richardson extrapolation
Download full preprint: PDF (1431 kB)
Abstract:
In the present paper we present the tensor-product approximation of
multi-dimensional convolution transform discretized via
collocation-projection
scheme on the uniform or composite refined grids.
Examples of convolving kernels are given by the classical Newton,
Slater (exponential) and Yukawa potentials,
,
and
with
.
For piecewise constant elements on the uniform grid of size
,
we prove the quadratic convergence
in the mesh parameter
h=1/n, and then justify the Richardson
extrapolation method on a sequence of grids that improves the order of
approximation up to
.
The fast algorithm of complexity
is described
for tensor-product convolution on the uniform/composite grids of size
,
where
are tensor ranks of convolving functions.
We also present the tensor-product convolution scheme in the two-level
Tucker-canonical format and discuss the consequent rank reduction strategy.
Finally, we give numerical illustrations confirming:
(a) the approximation
theory for convolution schemes of order
and
;
(b) linear-logarithmic scaling
of 1D discrete convolution on composite grids;
(c) linear-logarithmic scaling in n of our tensor-product
convolution method on
grid in the
range
.