Fast multidimensional convolution in low-rank formats via cross approximation

Abstract

We propose a new cross-conv algorithm for approximate computation of convolution in different low-rank tensor formats (tensor train, Tucker, Hierarchical Tucker). It has better complexity with respect to the tensor rank than previous approaches. The new algorithm has a high potential impact in different applications. The key idea is based on applying cross approximation in the "frequency domain", where convolution becomes a simple elementwise product. We illustrate efficiency of our algorithm by computing the three-dimensional Newton potential and by presenting preliminary results for solution of the Hartree-Fock equation on tensor-product grids.

14 pages, 2 figures

Cited by in corpus (4)

• Tensor Numerical Methods for High-dimensional PDEs: Basic Theory and Initial Applications
• Fast low-rank approximations of multidimensional integrals in ion-atomic collisions modelling
• Superfast CUR Matrix Algorithms, Their Pre-Processing and Extensions
• Tensor Numerical Approach to Linearized Hartree-Fock Equation for Lattice-type and Periodic Systems