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}/{\|x\|} $, $e^{-\lambda \|x\|} $ and ${e^{-\lambda\|x\| }}/{\|x\|} $ 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\leq 16384 $.