Inexact methods for the low rank solution to large scale Lyapunov equations
For computational scientists solving large-scale Lyapunov equations, this work offers a theoretically grounded relaxation strategy to reduce computational cost, though it is an incremental improvement over existing methods.
The paper develops a relaxation strategy for inexact solves in the rational Krylov subspace method and low-rank alternating directions implicit iteration for large-scale Lyapunov equations, providing practical tolerance choices and numerical validation.
The rational Krylov subspace method (RKSM) and the low-rank alternating directions implicit (LR-ADI) iteration are established numerical tools for computing low-rank solution factors of large-scale Lyapunov equations. In order to generate the basis vectors for the RKSM, or extend the low-rank factors within the LR-ADI method the repeated solution to a shifted linear system is necessary. For very large systems this solve is usually implemented using iterative methods, leading to inexact solves within this inner iteration. We derive theory for a relaxation strategy within these inexact solves, both for the RKSM and the LR-ADI method. Practical choices for relaxing the solution tolerance within the inner linear system are then provided. The theory is supported by several numerical examples.