Multilevel Toeplitz matrices generated by QTT tensor-structured vectors and convolution with logarithmic complexity
Metadata only
Date
2011Type
- Report
ETH Bibliography
yes
Altmetrics
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 220 × 220 × 220 points in 3D. Show more
Publication status
unpublishedJournal / series
Preprint / Max-Planck-InstitutVolume
Publisher
Max-Planck-Institut für Mathematik in den NaturwissenschaftenSubject
Toeplitz matrices; Circulant matrices; Convolution; Tensorisation; Virtual levels; Tensor decompositions; Tensor rank; Low-rank representation; Newton potential; Tensor Train; TT; Quantics Tensor Train; QTTOrganisational unit
03435 - Schwab, Christoph / Schwab, Christoph
More
Show all metadata
ETH Bibliography
yes
Altmetrics