MiS Preprint Repository

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, $1/\Vert x\Vert$, $e^{-\lambda \Vert x\Vert }$ and $e^{-\lambda \Vert x\Vert }/\Vert x\Vert$ with $x\in {\mathbb{R}}^d$.

For piecewise constant elements on the uniform grid of size $n^d$, we prove the quadratic convergence $O(h^2)$ 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 $O(h^3)$.

The fast algorithm of complexity $O(d{R}_1{R}_{2}n\log n)$ is described for tensor-product convolution on the uniform/composite grids of size $n^d$, where $R_1,R_2$ 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 $n\times n\times n$ grid in the range $n\le 16384$.