Volume 62, pp. 119-137, 2024.

Inexact linear solves in the low-rank alternating direction implicit iteration for large Sylvester equations

Patrick Kürschner

Abstract

We consider iteration for approximately solving large-scale algebraic Sylvester equations. Inside every iteration step of this iterative process, a pair of linear systems of equations has to be solved. We investigate the situation when those inner linear systems are solved inexactly by an iterative method such as, for example, preconditioned Krylov subspace methods. The main contribution of this work are thresholds for the required accuracies regarding the inner linear systems, which dictate when the employed inner Krylov subspace methods can be safely terminated. The goal is to save computational effort by solving the inner linear system as inaccurately as possible without endangering the functionality of the low-rank Sylvester–ADI method. Ideally, the inexact ADI method mimics the convergence behavior of the more expensive exact ADI method, where the linear systems are solved directly. Alongside the theoretical results, strategies for an actual practical implementation of the stopping criteria are also developed. Numerical experiments confirm the effectiveness of the proposed strategies.

Full Text (PDF) [454 KB], BibTeX

Key words

Sylvester equation, alternating direction implicit, low-rank approximation, inner–outer methods

AMS subject classifications

15A06, 15A24, 65F45, 65F55

Links to the cited ETNA articles

[7]	Vol. 43 (2014-2015), pp. 142-162 Peter Benner, Patrick Kürschner, and Jens Saak: Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations
[10]	Vol. 45 (2016), pp. 107-132 Tobias Breiten, Valeria Simoncini, and Martin Stoll: Low-rank solvers for fractional differential equations

< Back