MiS Preprint Repository

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.