A Parameter Free ADI-Like Method for the Numerical Solution of Large Scale Lyapunov Equations

This work presents an algorithm for constructing an approximate numerical solution to a large scale Lyapunov equation in low rank factored form. The algorithm is based upon a synthesis of an approximate power method and an alternating direction implicit (ADI) method. The former is parameter free and tends to be efficient in practice but there is little theoretical understanding of its convergence properties. The ADI method has a well-understood convergence theory, but the method relies upon selection of shift parameters and a poor shift selection can lead to very slow convergence in practice. The algorithm presented here uses an approximate power method iteration to obtain a basis update and then constructs a re-weighting of this basis to provide a factorization update that satisfies ADI-like convergence properties.