A Low-rank ADI Algorithm for the Numerical Solution of Large Discrete-time Non-symmetric Algebraic Riccati Equations

Abstract

Discrete-time non-symmetric algebraic Riccati equations (DTNAREs) arise in game-theoretic computations of Nash equilibria. Solving such equations at large scale is often computationally prohibitive. This paper develops a numerical approach for large-scale DTNAREs whose solutions are low rank. A low-rank alternating direction implicit (ADI) method is introduced that recursively constructs a low-rank stabilizing solution without explicitly solving any projected DTNARE. Through the pole-placement property of the low-rank ADI iteration, the method ensures that the implicitly solved projected DTNARE always admits a stabilizing solution. An automatic shift-generation strategy is also developed for the ADI iterations. Once an initial shift is provided, the algorithm computes the low-rank solution without further user intervention. Numerical experiments on DTNAREs with dimensions between \(10^6\) and \(10^7\) demonstrate the accuracy and efficiency of the method. The results confirm that the proposed low-rank ADI algorithm is an effective solver for large-scale DTNAREs that would otherwise be computationally prohibitive.