TY - JOUR
T1 - Solving large-scale nonsymmetric algebraic riccati equations by doubling
AU - Li, Tiexiang
AU - Chu, Eric King Wah
AU - Kuo, Yueh Cheng
AU - Lin, Wen-Wei
PY - 2013
Y1 - 2013
N2 - We consider the solution of the large-scale nonsymmetric algebraic Riccati equation XCX - XD - AX + B = 0, with M ≡ [D,-C;-B,A] ∈ ℝ 1+n2)×(n1+n2) being a nonsingular M-matrix. In addition, A and D are sparselike, with the products A-1u, A-Tu, D-1v, and D-Tv computable in O(n) complexity (with n = max{ n1, n2}), for some vectors u and v, and B,C are low ranked. The structure-preserving doubling algorithms (SDA) by Guo, Lin, and Xu [Numer. Math., 103 (2006), pp. 392-412] is adapted, with the appropriate applications of the Sherman-Morrison- Woodbury formula and the sparse-plus-low-rank representations of various iterates. The resulting large-scale doubling algorithm has an O(n) computational complexity and memory requirement per iteration and converges essentially quadratically. A detailed error analysis, on the effects of truncation of iterates with an explicit forward error bound for the approximate solution from the SDA, and some numerical results will be presented.
AB - We consider the solution of the large-scale nonsymmetric algebraic Riccati equation XCX - XD - AX + B = 0, with M ≡ [D,-C;-B,A] ∈ ℝ 1+n2)×(n1+n2) being a nonsingular M-matrix. In addition, A and D are sparselike, with the products A-1u, A-Tu, D-1v, and D-Tv computable in O(n) complexity (with n = max{ n1, n2}), for some vectors u and v, and B,C are low ranked. The structure-preserving doubling algorithms (SDA) by Guo, Lin, and Xu [Numer. Math., 103 (2006), pp. 392-412] is adapted, with the appropriate applications of the Sherman-Morrison- Woodbury formula and the sparse-plus-low-rank representations of various iterates. The resulting large-scale doubling algorithm has an O(n) computational complexity and memory requirement per iteration and converges essentially quadratically. A detailed error analysis, on the effects of truncation of iterates with an explicit forward error bound for the approximate solution from the SDA, and some numerical results will be presented.
KW - Doubling algorithm
KW - M-matrix
KW - Nonsymmetric algebraic Riccati equation
KW - Numerically low-ranked solution
UR - http://www.scopus.com/inward/record.url?scp=84887387728&partnerID=8YFLogxK
U2 - 10.1137/110858070
DO - 10.1137/110858070
M3 - Article
AN - SCOPUS:84887387728
SN - 0895-4798
VL - 34
SP - 1129
EP - 1147
JO - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
IS - 3
ER -