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.
Introduction
Multidimensional convolution is a fundamental operation in scientific computing, essential for applications ranging from population dynamics to quantum chemistry. However, it is notoriously susceptible to the "curse of dimensionality." In a standard 3D grid with $n$ points per dimension, a naive convolution requires $O(n^6)$ operations. Even the Fast Fourier Transform (FFT), while more efficient at $O(n^d \log n)$, becomes computationally prohibitive as the dimension $d$ or the resolution $n$ increases.
Low-rank tensor formats, such as Tensor Train (TT) or Tucker, offer a way to compress these massive datasets. However, convolving two low-rank tensors typically results in a new tensor whose rank is the product of the input ranks ($r_1 \times r_2$). The subsequent need to re-compress this "rank-exploded" result often becomes the primary computational bottleneck. This paper introduces cross-conv, an algorithm designed to bypass this explosion by performing operations in the frequency domain using cross approximation.
The Cross-Conv Algorithm
The cross-conv method relies on the convolution theorem, which states that convolution in the spatial domain is equivalent to element-wise multiplication in the frequency domain. The workflow consists of three primary stages:
- Frequency Domain Transformation: The input tensors are transformed using the FFT. A critical observation of this work is that the FFT is a tensor-product operator. Consequently, it preserves the low-rank structure and the specific ranks of the input tensors, making the frequency domain a "safe haven" for low-rank representations.
- Cross Approximation Multiplication: In the frequency domain, the convolution is reduced to an element-wise (Schur) product. Rather than computing every single element of this product—which would lead to the multiplicative rank growth mentioned earlier—the authors employ cross approximation. By sampling only a small subset of elements, the algorithm reconstructs the low-rank result directly. This keeps computational complexity linear or quadratic relative to the rank, rather than multiplicative.
- Inverse Transformation: Finally, an inverse FFT is applied to the cores of the resulting low-rank tensor to return the data to the spatial domain.
For the Tucker format specifically, the paper introduces Schur-Cross3D, an optimized implementation that achieves an improved asymptotic complexity of $O(nr^2 + r^4)$.
Experimental Evaluation
The authors validated the cross-conv algorithm across several demanding benchmarks:
Synthetic and Molecular Potentials
The algorithm was tested using a 3D Newton potential of a Slater function ($e^{-\zeta|y|}$) and precomputed Tucker-format densities for various molecules, including Methane ($CH_4$), Ethane ($C_2H_6$), Ethanol ($C_2H_5OH$), and Nitroethane ($C_2H_5NO_2$). These tests were performed on massive $5121^3$ grids, representing over 134 billion grid points. The cross-conv algorithm successfully computed the Newton potential for these complex molecules in a timeframe of 1.2 to 19.8 seconds on standard desktop hardware.
Quantum Chemistry Applications
To test the utility of the method in iterative solvers, the authors applied it to the Hartree-Fock equation for a Helium atom. The method maintained high precision, achieving a relative error within $10^{-6}$, matching theoretical limits as grid resolution increased.
Key Insights and Comparisons
A significant finding of this research is the comparison between cross-conv and Quantized Tensor Train (QTT) methods. While QTT offers superior theoretical asymptotic complexity ($O(\log n)$), the authors demonstrate that for practical grid sizes ($n \approx 10^3$ to $10^4$), cross-conv is significantly faster. This is attributed to the much smaller hidden constants in the cross-conv algorithm's complexity profile.
Furthermore, the success of the method hinges on the "sampling" principle: because the resulting tensor is expected to be low-rank, it is not necessary to compute the entire product to understand its structure. Cross-approximation effectively identifies the most informative elements to reconstruct the whole.
Conclusion and Future Work
The cross-conv algorithm provides a highly efficient pathway for multidimensional convolution, effectively mitigating rank explosion. While the method assumes that the convolution result can be represented in a low-rank format—a condition generally met by smooth kernels like the Newton potential—future work will focus on expanding its application to more complex systems. This includes the Smoluchowski coagulation equation and full-scale Kohn-Sham equations for larger molecular structures. The authors have released an open-source implementation of the Tucker3D toolbox to facilitate further research in this area.
Summary updated