Multilevel Toeplitz matrices generated by QTT tensor-structured vectors and convolution with logarithmic complexity

Vladimir A. Kazeev, Boris N. Khoromskij, and Eugene E. Tyrtyshnikov

Contact the author: Please use for correspondence this email.
Submission date: 19. Jun. 2011 (revised version: August 2011)
Pages: 33
published in: SIAM journal on scientific computing, 35 (2013) 3, p. A1511-A1536 
DOI number (of the published article): 10.1137/110844830
Bibtex
with the following different title: Multilevel Toeplitz matrices generated by tensor-structured vectors and convolution with logarithmic complexity
MSC-Numbers: 15A69, 15B05, 44A35, 65F99
Keywords and phrases: Toeplitz matrices, circulants, convolution, low-rank representation, virtual levels, tensor decompositions, Tensor Train (TT), Quantized Tensor Train (QTT), newton potential
Download full preprint: PDF (413 kB)

Abstract:
We consider two operations in the QTT format: composition of a multilevel Toeplitz matrix generated by a given multidimensional vector and convolution of two given multidimensional vectors. We show that low-rank QTT structure of the input is preserved in the output and propose efficient algorithms for these operations in the QTT format.

For a d-dimensional 2n ×… × 2n-vector x given in a QTT representation with ranks bounded by p we show how a multilevel Toeplitz matrix generated by x can be obtained in the QTT format with ranks bounded by 2p in operations. We also describe how the convolution x ⋆ y of x and a d-dimensional n×…×n-vector y can be computed in the QTT format with ranks bounded by 2t in operations, provided that the matrix xy′ is given in a QTT representation with ranks bounded by t. We exploit approximate matrix-vector multiplication in the QTT format to accelerate the convolution algorithm dramatically.

We demonstrate high performance of the convolution algorithm with numerical examples including computation of the Newton potential of a strong cusp on fine grids with up to 2²⁰ × 2²⁰ × 2²⁰ points in 3D.