Efficient handling of complex shift parameters in the low-rank Cholesky factor ADI method / Peter Benner, Patrick Kürschner, Jens Saak

Abstract

Abstract: The solution of large-scale Lyapunov equations is a crucial problem for several fields of modern applied mathematics. The low-rank Cholesky factor version of the alternating directions implicit method (LRCF-ADI) is one iterative algorithm that computes approximate low-rank factors of the solution. In order to achieve fast convergence it requires adequate shift parameters, which can be complex if the matrices defining the Lyapunov equation are unsymmetric. This will require complex arithmetic computations as well as storage of complex data and thus, increase the overall complexity and memory requirements of the method. In this article we propose a novel reformulation of LRCF-ADI which generates real low-rank factors by carefully exploiting the dependencies of the iterates with respect to pairs of complex conjugate shift parameters. It significantly reduces the amount of complex arithmetic calculations and requirements for complex storage. It is hence often superior in terms of efficiency compared to other real formulations.