Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension
type: Item
instance of: scholarly article
title: Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension
zbMATH Open document ID: 1197.65216
author: Boris N. Khoromskij
published in: Journal of Computational and Applied Mathematics
publication date: 2010-08-27T00:00:00Z
review text: 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\).
reviewed by: Titus Petrila
Mathematics Subject Classification ID: 65R10
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 44A35
Mathematics Subject Classification ID: 44A30
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 15A69
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 5775752
zbMATH Keywords: Kronecker products
zbMATH Keywords: Tucker tensor decomposition
zbMATH Keywords: canonical tensors
zbMATH Keywords: multidimensional convolution
zbMATH Keywords: collocation-projection method
zbMATH Keywords: Richardson extrapolation
zbMATH Keywords: composite grids
zbMATH Keywords: numerical examples
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: Newton potential
zbMATH Keywords: Slater potential
zbMATH Keywords: tensor-product approximation
zbMATH Keywords: convolution transform
zbMATH Keywords: Yukawa potentials
zbMATH Keywords: quadratic convergence
zbMATH Keywords: complexity
zbMATH Keywords: tensor-product convolution
MaRDI profile type: Publication
full work available at URL: j.cam.2010.02.004
OpenAlex ID: W1967807484
cites work: Approximating a wavefunction as an unconstrained sum of Slater determinants
cites work: On tensor approximation of Green iterations for Kohn-Sham equations
cites work: Multigrid Accelerated Tensor Approximation of Function Related Multidimensional Arrays
cites work: Numerical operator calculus in higher dimensions
cites work: Hierarchical Kronecker tensor-product approximations
cites work: Hierarchical tensor-product approximation to the inverse and related operators for high-dimensional elliptic problems
cites work: Structured Rank-(r1, . . . , rd) Decomposition of Function-related Tensors in R_D
cites work: Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators I. Separable approximation of multi-variate functions
cites work: Low rank Tucker-type tensor approximation to classical potentials
cites work: Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time
cites work: Q3152895
cites work: On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
cites work: Verification of the cross 3D algorithm on quantum chemistry data
cites work: Tensor Decompositions and Applications
cites work: Rank-one approximation to high order tensors
cites work: Fast and exact projected convolution for non-equidistant grids
cites work: Tensor decomposition in electronic structure calculations on 3D Cartesian grids
cites work: A Multilinear Singular Value Decomposition
cites work: Linear algebra for tensor problems
DOI: 10.1016/J.CAM.2010.02.004
description: scientific article; zbMATH DE number 5775752