Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
36/2011

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

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

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 \times\ldots\times 2n$-vector $\boldsymbol{x}$ given in a QTT representation with ranks bounded by $p$ we show how a multilevel Toeplitz matrix generated by $\boldsymbol{x}$ can be obtained in the QTT format with ranks bounded by $2p$ in $\mathcal{O}\left(dp^{2} \log n\right)$ operations. We also describe how the convolution $\boldsymbol{x}\star\boldsymbol{y}$ of $\boldsymbol{x}$ and a $d$-dimensional $n \times\ldots\times n$-vector $\boldsymbol{y}$ can be computed in the QTT format with ranks bounded by $2t$ in $\mathcal{O}\left(dt^{2} \log n\right)$ operations, provided that the matrix $\boldsymbol{x}\boldsymbol{y'}$ 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^{20} \times 2^{20} \times 2^{20}$ points in 3D.

Received:
Jun 19, 2011
Published:
Jun 20, 2011
MSC Codes:
15A69, 15B05, 44A35, 65F99
Keywords:
Toeplitz matrices, circulants, convolution, low-rank representation, virtual levels, tensor decompositions, Tensor Train (TT), Quantized Tensor Train (QTT), newton potential

Related publications

inJournal
2013 Repository Open Access
Vladimir A. Kazeev, Boris N. Khoromskij and Eugene E. Tyrtyshnikov

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

In: SIAM journal on scientific computing, 35 (2013) 3, A1511-A1536