Low rank solution of Lyapunov equations

Jacob White and Jing-Rebecca Li
december, 2004
Publication type:
Paper in peer-reviewed journals
SIAM Review, vol. 46(4), pp. 693–713
This paper presents the Cholesky factor--alternating direction implicit (CF--ADI) algorithm, which generates a low-rank approximation to the solution X of the Lyapunov equation AX+XAT = -BBT. The coefficient matrix A is assumed to be large, and the rank of the right-hand side -BBT is assumed to be much smaller than the size of A. The CF--ADI algorithm requires only matrix-vector products and matrix-vector solves by shifts of A. Hence, it enables one to take advantage of any sparsity or structure in A. This paper also discusses the approximation of the dominant invqrian| 3ubspace of the solution X. We characterize a group of spanning sets for the range of X. A connection is made between the approximation of the dominant invariant subspace of X and the generation of various low-order Krylov and rational Krylov subspaces. It is shown by numerical examples that the rational Krylov subspace generated by the CF--ADI algorithm, where the shifts are obtained as the solution of a rational minimax problem, often gives the best approximation to the dominant invariant subspace of X. Copyright © 2004 Society for Industrial and Applied Mathematics
    author={Jacob White and Jing-Rebecca Li },
    title={Low rank solution of Lyapunov equations },
    doi={10.1137/S0036144504443389 },
    journal={SIAM Review },
    year={2004 },
    volume={46(4) },