Krylov Subspace Methods for Solving Large Lyapunov Equations

Abstract

This paper considers several methods for calculating low-rank approximate solutions to large-scale Lyapunov equations of the form $AP + PA' + BB' = 0$. The interest in this problem stems from model reduction where the task is to approximate high-dimensional models by ones of lower order. The two recently developed Krylov subspace methods exploited in this paper are the Arnoldi method [Saad, Math. Comput., 37 (1981), pp. 105–126] and the Generalised Minimum Residual method (GMRES) [Saad and Schultz, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856–869]. Exact expressions for the approximation errors incurred are derived in both cases. The numerical solution of the low-dimensional linear matrix equation arising from the GMRES method is discussed and an algorithm for its solution is proposed. Low rank solutions of discrete time Lyapunov equations and continuous time algebraic Riccati equations are also considered. Throughout this paper, the authors tackle problems in which B has more than one column with the use of block Krylov schemes.