$LDL^\top$ Factorization-based Generalized Low-rank ADI Algorithm for Solving Large-scale Algebraic Riccati Equations

Abstract

The low-rank alternating direction implicit (ADI) method is an efficient and effective solver for large-scale standard continuous-time algebraic Riccati equations that admit low-rank solutions. However, the existing low-rank ADI algorithm for Riccati equations (RADI) cannot be directly applied to general-form Riccati equations. This paper introduces a generalized RADI algorithm based on an $LDL^\top$ factorization, which efficiently handles the general Riccati equations arising in important applications like state estimation and controller design. An efficient implementation is presented that avoids the Sherman-Morrison-Woodbury formula and instead uses a low-rank Cholesky factor ADI method as the base algorithm to compute low-rank factors of general-form Riccati equations. Sample MATLAB-based implementations of the proposed algorithm are also provided. An approach for automatically and efficiently generating ADI shifts is discussed. Numerical examples solving several Riccati equations of orders ranging from $10^6$ to $10^7$ accurately and efficiently are presented, demonstrating the effectiveness of the proposed algorithm.