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

The author presents a tensor-product approximation of a multidimensional convolution transform discretized via a collocation-projection 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^{-\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}\), he proves quadratic convergence \(O(h^{2})\) in the mesh parameter \(h=1/n\), and then justifies 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_{1}R_{2}n\log{n})\) is described for tensor-product convolution on uniform/composite grids of size \(n^{d}\), where \(R_{1}\), \(R_{2}\) are tensor ranks of convolving functions. The author also presents the tensor-product convolution scheme in the two-level Tucker canonical format and discusses the consequent rank reduction strategy. Finally, he gives 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\times n\times n\) grid in the range \(n\leq16384\).