On bounds for rank growth of iterands in conjugate gradients for Lyapunov equation

Abstract

We focus on solving the Lyapunov equation $AX+X{A}^T=F$, where $A$, $X$ and $F$ are square matrices, $A$ is symmetric positive definite (SPD) and sparse, and $F$ is symmetric and of a low-rank. The solution $X$ is then also symmetric and in general dense, but it can be approximated by a low-rank matrix. If $n$ is large, $X$ cannot be computed directly, but it is accessible by using the so-called low-rank arithmetics (LRA). The equation is solved by matrix reformulation of the method of conjugate gradients (MCG). We are interested in the behavior of ranks of the solution approximations $X_{\ell }$, residuals $R_{\ell }$, and direction vectors $P_{\ell }$ during iterations.

1 figure