Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension
✍ Scribed by Boris N. Khoromskij
- Book ID
- 104007056
- Publisher
- Elsevier Science
- Year
- 2010
- Tongue
- English
- Weight
- 718 KB
- Volume
- 234
- Category
- Article
- ISSN
- 0377-0427
No coin nor oath required. For personal study only.
✦ Synopsis
In the present paper we present the 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 -λ x and e -λ x / x with x ∈ R d . For piecewise constant elements on the uniform grid of size n d , we prove 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 ). 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. We also present the tensor-product convolution scheme in the twolevel 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.