Low-rank solution of Lyapunov equations. (English) Zbl 1068.65053

Li, Jing-Rebecca; White, Jacob

SIAM Rev. 46, No. 4, 693-713 (2004).

The paper concerns the Cholesky factor-alternating direction implicit (CF-ADI) algorithm, which generates a low-rank approximation to the solution \(X\) of the large-scale Lyapunov equation, whose right-hand side have low rank: \[ AX+XA^T=-BB^T\quad A\in \mathbb{R}^{n\times n},\;X\in \mathbb{R}^n\tag{1} \] and the connection between the approximation of the dominant invariant subspace of \(X\) and the generation of various low-order Krylov and rational Krylov subspaces.
The first section represents an introduction to this type of equation (1), for the case when the coefficient matrix \(A\) is large and stable, \(\lambda_i<0\), \((\forall)i\).
The second section motivates the solution of the Lyapunov equation and the approximation of the dominant invariant subspace of the solution in the context of linear, time-invariant systems.
The third section provides background on existing approaches to the solution of (1), including the ADI algorithm in some detail and low-rank methods.
Section four develops the CF-ADI algorithm, which is more efficient than the ADI method described in the section three, because it iterates on the Cholesky factor of the ADI approximation rather than on the ADI approximation itself. Numerical results are presented on the CF-ADI approximation to the solution to (1).
Section five contains a collection of definitions and useful results concerning Krylov and rational Krylov subspaces.
Section six characterizes spanning sets for a subspace based on \(A\) and \(B\).
The seventh section shows that these spanning sets also span the range of \(X\) and uses that result to prove several properties of CF-ADI.
The eigth section makes the connection between the approximation of the dominant invariant subspace of \(X\) and the generation of various low-order Krylov and rational Krylov subspaces. Numerical examples are presented of several different-Krylov and rational Krylov subspace approximations.
The last section contains the conclusions.

Reviewer: R. Militaru (Craiova)

MSC:

65F30	Other matrix algorithms (MSC2010)
65F10	Iterative numerical methods for linear systems
15A24	Matrix equations and identities
93C05	Linear systems in control theory

Keywords:

Lyapunov equation; implicit iteration; low-rank approximation; invariant subspace; iterative methods; Cholesky factor-alternating direction implicit algorithm; rational Krylov subspaces; linear, time-invariant systems; numerical results