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.
