A Unified Low-rank ADI Framework with Shared Linear Solves for Simultaneously Solving Multiple Lyapunov, Sylvester, and Riccati Equations

Abstract: It is known in the literature that the low-rank ADI method for Lyapunov equations is a Petrov-Galerkin projection algorithm that implicitly performs model order reduction. In this paper, we show that the low-rank ADI methods for Sylvester and Riccati equations are also Petrov-Galerkin projection algorithms that implicitly perform model order reduction. By observing that the ADI methods for Lyapunov, Sylvester, and Riccati equations differ only in pole placement and not in their interpolatory nature, we show that the shifted linear solves-which constitute the bulk of the computational cost-can be shared. The pole-placement step involves only small-scale operations and is therefore inexpensive. We propose a unified ADI framework that requires only two shifted linear solves per iteration to simultaneously solve six Lyapunov equations, one Sylvester equation, and ten Riccati equations, thus substantially increasing the return on investment for the computational cost spent on the linear solves. All operations needed to extract the individual solutions from these shared linear solves are small-scale and inexpensive. Since all ADI methods implicitly perform model order reduction when solving these linear matrix equations, we show that the resulting reduced-order models can be obtained as an additional byproduct. These models not only interpolate the original transfer function at the mirror images of the ADI shifts but also preserve important system properties such as stability, minimum-phase property, positive-realness, bounded-realness, and passivity. Consequently, the proposed unified ADI framework also serves as a recursive, interpolation-based model order reduction method, which can preserve several important properties of the original model in the reduced-order model.