Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension

摘要

In the present paper we present the tensor-product approximation of a multidimensional convolution transform discretized via a collocationprojection scheme on uniform or composite refined grids. Examples of convolving kernels are provided by the classical Newton, Slater (exponential) and Yukawa potentials, 1||x||, e-λ||x|| and e-λ||x||||x|| with x∈Rd. For piecewise constant elements on the uniform grid of size nd, we prove quadratic convergence O(h~2) in the mesh parameter h=1n, and then justify the Richardson extrapolation method on a sequence of grids that improves the order of approximation up to O(h~3). A fast algorithm of complexity O(dR _1R_1nlogn) is described for tensor-product convolution on uniform/composite grids of size n~d, where R1,R2 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 O(h~2) and O(h~3); (b) linear-logarithmic scaling of 1D discrete convolution on composite grids; (c) linear-logarithmic scaling in n of our tensor-product convolution method on an n×n×n grid in the range n≤16384.