TY  - JOUR
A1  - Kürschner, Patrick
A1  - Freitag, Melina A.
T1  - Inexact methods for the low rank solution to large scale Lyapunov equations
T2  - BIT : numerical mathematics ; the leading applied mathematics journal for all computational mathematicians
N2  - 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 of equations is necessary. For very large systems this solve is usually implemented using iterative methods, leading to inexact solves within this inner iteration (and therefore to "inexact methods"). We will show that one can terminate this inner iteration before full precision has been reached and still obtain very good accuracy in the final solution to the Lyapunov equation. In particular, for both the RKSM and the LR-ADI method we derive theory for a relaxation strategy (e.g. increasing the solve tolerance of the inner iteration, as the outer iteration proceeds) within the iterative methods for solving the large linear systems. These theoretical choices involve unknown quantities, therefore practical criteria for relaxing the solution tolerance within the inner linear system are then provided. The theory is supported by several numerical examples, which show that the total amount of work for solving Lyapunov equations can be reduced significantly.
KW  - Lyapunov equation
KW  - alternating direction implicit
KW  - rational Krylov
KW  - subspaces
KW  - low-rank approximations
Y1  - 2020
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/60321
SN  - 0006-3835
SN  - 1572-9125
VL  - 60
IS  - 4
SP  - 1221
EP  - 1259
PB  - Springer
CY  - Dordrecht
ER  -