A New Generalized Low-Rank Cholesky Factor ADI Algorithm for Large-Scale Stein Equations

Abstract

The low-rank alternating direction implicit (ADI) method is an efficient solver for large-scale Stein equations with low-rank solutions. This paper shows that, as in the continuous-time Lyapunov equation case, the low-rank Cholesky factor ADI (LRCF-ADI) method for Stein equations implicitly performs $\mathcal{H}_2$-pseudo-optimal model order reduction for discrete-time systems. This observation leads to an automatic shift-generation strategy, allowing LRCF-ADI to select subsequent shifts without user intervention. The standard LRCF-ADI method requires shifts outside the unit circle. We generalize the method to allow shifts anywhere in the complex plane, including on the unit circle. This extension enables numerical integration for frequency-limited Stein equations by interpolating the integrand at points on the unit circle. It also enables non-intrusive, data-driven balanced truncation and frequency-limited balanced truncation using experimentally measurable transfer function samples on the unit circle, without requiring access to a state-space realization. Numerical results for large-scale models demonstrate the effectiveness of the proposed methods as low-rank Stein equation solvers and data-driven model order reduction methods.