Direct numerical solution of algebraic Lyapunov equations for large-scale systems using Quantized Tensor Trains

We present a novel method for solving high-dimensional algebraic Lyapunov equations exploiting the recently proposed Quantized Tensor Train (QTT) numerical linear algebra. A key feature of the approach is that given a prescribed error tolerance, it automatically calculates the optimal lowest rank approximation of the solution in the Frobenius norm. The low rank nature of the approximation potentially enables a sublinear scaling of the computational complexity with the number of states of the dynamical system. The resulting solutions appear in a new matrix tensor format which we call the Vectorized-QTT-Matrix format. We show the effectiveness of our method by calculating the controllability Gramians for discretized reaction-diffusion equations. We introduce an algorithm for the new tensor format of the solution for calculating the matrix-by-vector product and combine it with the celebrated Lanczos algorithm to compute the dominant eigenvalues/eigenvectors of the matrix.