Multilevel Toeplitz Matrices Generated by Tensor-Structured Vectors and Convolution with Logarithmic Complexity

We study the tensor structure of two operations: the transformation of a given multidimensional vector into a multilevel Toeplitz matrix and the convolution of two given multidimensional vectors. We show that the low-rank tensor structure of the input is preserved in the output and propose efficient algorithms for these operations in the newly introduced quantized tensor train (QTT) format. Consider a d-dimensional 2n ×⋯× 2n-vector x. If it is represented elementwise, the number of parameters is (2n)ᵈ. However, if we assume that x is given in a QTT representation with ranks bounded by p, the number of parameters is reduced to O(dp² log n). Under this assumption we show how the multilevel Toeplitz matrix generated by x can be obtained in the QTT format with ranks bounded by $2p$ in O(dp² log n) operations. We also describe how the convolution x of x and a d-dimensional n ×⋯× n-vector y can be computed in the QTT format with ranks bounded by $2t$ in O(dt² log n) operations, provided that the matrix xy' is given in the same format with ranks bounded by t. We exploit an algorithm for the inexact matrix-vector multiplication in the QTT format to accelerate the convolution algorithm dramatically. The performance of our approach to convolution is demonstrated with numerical examples, including the computation of the Newton potential of a strong cusp on fine grids with up to 2²⁰ × 2²⁰ × 2²⁰ points in three dimensions.