Structured Doubling Algorithm for a Class of Large-Scale Discrete-Time Algebraic Riccati Equations with High-Ranked Constant Term

Consider the computation of the solution for a class of discrete-time algebraic Riccati equations (DAREs) with the low-ranked coefficient matrix G and the high-ranked constant matrix H. A structured doubling algorithm is proposed for large-scale problems when A is of lowrank. Compared to the existing doubling algorithm of O(2(k)n) flops at the k-th iteration, the newly developed version merely needs O(n) flops for preprocessing and O((k+1)(3)m(3)) flopsfor iterations and is more proper for large-scale computations when mMUCH LESS-THANn. The convergence and complexity of the algorithm are subsequently analyzed. Illustrative numerical experiments indicate that the presented algorithm, which consists of a dominant time-consuming preprocessing step and a trivially iterative step, is capable of computing the solution efficiently for large-scale DAREs.

Automated summary

This paper presents a computational method for a class of discrete-time algebraic Riccati equations (DAREs) with a low-ranked coefficient matrix G and a high-ranked constant matrix H, using a structured doubling algorithm to solve large-scale problems. Compared to the existing doubling algorithm with O(2(k)n) flops at the k-th iteration, the newly developed version requires only O(n) flops for preprocessing and O((k+1)(3)m(3)) flops for iterations, making it more suitable for large-scale computations when mMUCH LESS-THANn. The convergence and complexity of the algorithm are subsequently analyzed. Illustrative numerical experiments show that the presented algorithm, which consists of a dominant time-consuming preprocessing step and a trivially iterative step, is capable of efficiently computing the solution for large-scale DAREs.