Fast multidimensional convolution in low-rank formats via cross approximation
arXiv:1402.5649
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.
arXiv comment14 pages, 2 figures
References in corpus (4)
- Thermodynamic limit of the density matrix renormalization for the spin-1 Heisenberg chain
- Alternating minimal energy methods for linear systems in higher dimensions. Part II: Faster algorithm and application to nonsymmetric systems
- Alternating minimal energy methods for linear systems in higher dimensions. Part I: SPD systems
- Quasioptimality of maximum-volume cross interpolation of tensors
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