no. 16 · Tuesday 17 November 2026
G-RADI: A Low-Rank ADI Algorithm for General-Form Large-Scale Continuous-Time Algebraic Riccati Equations
Abstract
Continuous-time algebraic Riccati equations (CAREs) arise in numerous disciplines and can be written in several forms. When the coefficient matrices are small and dense, stabilizing solutions can be computed for all these forms. The situation differs for large-scale sparse problems: for CAREs in general form, only a reformulation of the Newton–Kleinman iteration is currently available. The low-rank alternating direction implicit (ADI) algorithm for CAREs, known as Riccati-ADI (RADI), is among the most successful and computationally efficient methods in the literature. However, RADI applies only to simplified forms of CAREs; no low-rank ADI algorithm is available for CAREs in general form. This paper presents a low-rank ADI algorithm for CAREs in general form, which contains RADI as a special case. Unlike the Newton–Kleinman iteration, which computes a new approximation at every step, the proposed algorithm—like RADI—recursively accumulates low-rank factors of an approximation to the stabilizing solution. Moreover, the residual admits a low-rank factorization, so its norm can be computed efficiently; in the Newton–Kleinman iteration, computing the residual norm is considerably more involved. An automatic shift-generation strategy is also proposed, enabling the algorithm to select its shifts without user input. Numerical experiments on benchmark problems with orders ranging from \(10^6\) to \(10^7\) show that the proposed method is accurate and computationally efficient, and that it outperforms the Newton–Kleinman iteration.
- fields
- Numerical Analysis