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.

M. Nip, J. P. Hespanha, and M. Khammash
Proceedings of the 52nd Conference on Decision and Control
Pages: 1950 - 1957
Date: December, 2013
ICB Affiliated Authors: João P Hespanha