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 .