Trail to a Lyapunov equation solver

AbstractThe Lyapunov matrix equation AX+XA⊤=B is N-stable when all eigenvalues of the real n×n matrix A have positive real part. When the real n×n matrix B is spd the solution X is spd. It is of low rank when B=CC⊤ where C is n×r with r≪n. An efficient algorithm has been found for solving the low-rank equation. This algorithm is a result of over fifty years of research starting with seemingly unrelated development of alternating direction implicit (ADI) iterative solution of elliptical systems. The low rank algorithm may be applied to a full rank equation if one can approximate the right-hand side by a sum of low rank matrices. This may be attempted with the Lanczos algorithm