Fast multidimensional convolution in low-rank formats via cross approximation
For researchers using low-rank tensor methods in scientific computing, this algorithm reduces computational cost for convolution operations, but the improvement is incremental.
The paper proposes a cross-conv algorithm for approximate convolution in low-rank tensor formats, achieving better complexity with respect to tensor rank than previous methods. It demonstrates efficiency on 3D Newton potential and Hartree-Fock equation computations.
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.