Alternating low-rank method for the Lyapunov equation


Time-stepping free method based on the rational Krylov subspaces play an important role in many applications. The adaptative selection of the shifts for the construction of the RKS is crucial. In this paper we propose a new algorithm for the selection of the shifts. It is based on the connection between the solution of the Lyapunov equation

$$ AX + XA^{\top} = y_0 y_0^{\top} $$

and the solution of a linear ODE

$$ \frac{dy}{dt} = Ay, \quad y(0) = y_0. $$

We have compared the efficiency of the new method with KPIK and RKSM methods (implementation were taken from the homepage of Valeria Simonchini. The ALR method we propose was the most efficient one (and it is parameter-free).


26/05/2016 A TT-eigenvalue solver that finally works
12/05/2016 Exponential machines and tensor trains
06/04/2016 Convergence analysis of a projected fixed-point iteration
30/03/2016 Compress-and-eliminate solver for sparse matrices
01/12/2015 New paper in SIMAX


We are located at the 2-nd floor of the new "Technopark-3” building in Skolkovo (few kilometers outside Moscow Ring Road). The building is accessible from Skolkovo Road (Сколковское шоссе) and Minskoe Highway (Минское шоссе).