# Low rank solution of Lyapunov equations

december, 2004

Publication type:

Paper in peer-reviewed journals

Journal:

SIAM Review, vol. 46(4), pp. 693â€“713

HAL:

Abstract:

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

BibTeX:

@article{Whi-Li-2004, author={Jacob White and Jing-Rebecca Li }, title={Low rank solution of Lyapunov equations }, doi={10.1137/S0036144504443389 }, journal={SIAM Review }, year={2004 }, month={12}, volume={46(4) }, pages={693â€“713}, }