Volume 51, pp. 240-261, 2019.

Approximate residual-minimizing shift parameters for the low-rank ADI iteration

Patrick Kürschner


The low-rank alternating directions implicit (LR-ADI) iteration is a frequently employed method for efficiently computing low-rank approximate solutions of large-scale Lyapunov equations. In order to achieve a rapid error reduction, the iteration requires shift parameters whose selection and generation is often a difficult task, especially for nonsymmetric matrices in the Lyapunov equation. This article represents a follow up of Benner et al. [Electron. Trans. Numer. Anal., 43 (2014–2015), pp. 142–162] and investigates self-generating shift parameters based on a minimization principle for the Lyapunov residual norm. Since the involved objective functions are too expensive to evaluate and hence intractable, objective functions are introduced which are efficiently constructed from the available data generated by the LR-ADI iteration. Several numerical experiments indicate that these residual-minimizing shifts using approximated objective functions outperform existing precomputed and dynamic shift parameter selection techniques, although their generation is more involved.

Full Text (PDF) [434 KB], BibTeX

Key words

Lyapunov equation, alternating directions implicit, low-rank approximation, shift parameters

AMS subject classifications

15A06, 65F10, 65F30

Links to the cited ETNA articles

[9]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
[19]Vol. 47 (2017), pp. 100-126 Andreas Frommer, Kathryn Lund, and Daniel B. Szyld: Block Krylov subspace methods for functions of matrices

< Back