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 106 and 107 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.
Related
- Numerical Solution of Large-Scale Low-Rank Coupled Generalized Sylvester Equations
- D-RADI: A Low-rank ADI Algorithm for Solving Large-scale Discrete-time Algebraic Riccati Equations
- Efficient Numerical Evaluation of Arbitrary High-order Partial Derivatives via Algebraic Decomposition
- A New Algebraic Algorithm for LWE
- A solution to the quantum Yang--Baxter equation associated with a universal two-valued algebraic group
BibTeX
@misc{zulfiqar2026lowrank,
title = {{A Low-rank ADI Algorithm for the Numerical Solution of Large Discrete-time Non-symmetric Algebraic Riccati Equations}},
author = {Umair Zulfiqar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21282},
eprint = {2609.21282},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21282},
}
RIS
TY - UNPB
TI - A Low-rank ADI Algorithm for the Numerical Solution of Large Discrete-time Non-symmetric Algebraic Riccati Equations
AU - Umair Zulfiqar
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21282
UR - https://arxiv.org/abs/2609.21282
AB - 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.
ER -