Low-Rank Explicit QTT Representation of the Laplace Operator and Its Inverse

Abstract

We focus on the construction of explicit low-rank representations of matrices in the tensor train (TT) and quantized tensor train (QTT) formats which have been proposed recently for the low-parametric structured representation of large-scale tensors. The matrices under consideration are discretizations of the Laplace operator in a hypercube (in one and many dimensions) and their inverses (in one dimension). For these matrices we derive explicit and exact QTT representations of low QTT ranks independent of the numbers $d$ and $n^{2}$ of dimensions and entries in each dimension. This implies that for the matrices considered the storage cost is $\mathcal{O}\left(d\,\log n\right)$, i.e., logarithmic with respect to the total number $n^{2d}$ of entries. The same applies to the computational complexity of the QTT-structured operations with these matrices, which now depends on the QTT ranks of the other operands. The general result of the paper is the notation and technique we introduce in order to examine the QTT structure of matrices analytically. They prove to be an efficient tool of studying other tensors related to particular computational problems, which are not considered in this paper.