Performance of Low-Rank Tensor Algorithms

Kurzfassung

We discuss low-rank tensor algorithms and in particular algorithms for the tensor-train (TT) format (known as MPS in computational physics). We focus on the required building blocks and model their node-level performance on modern multi-core CPUs. More specifically, we consider the lossy compression of large dense data (TT-SVD), as well as linear solvers in TT format (TT-MALS, TT-GMRES). For the data compression, we derive the optimal roofline runtime for the complete algorithm based on the two main building blocks in an optimized implementation: Q-less TSQR and tall-skinny matrix-matrix multiplication. For the low-rank linear solvers, we categorize the different kinds of building blocks according to performance characteristics and show possible performance optimizations. While all required tensor operations can be mapped onto standard BLAS/LAPACK routines theoretically, faster implementations need specific performance optimizations: These include (1) avoiding costly singular-value decompositions (SVDs), and (2) employing special fused operations for sequences of memory-bound tensor-contractions and reshaping operations, as well as (3) tracking properties of tensors such as orthogonalities. We show the effect of the different optimizations and compare the runtime of our implementation with other tensor libraries.