Solving large-scale nonsymmetric algebraic riccati equations by doubling

Tiexiang Li*, Eric King Wah Chu, Yueh Cheng Kuo, Wen-Wei Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)1129-1147
Number of pages19
JournalSIAM Journal on Matrix Analysis and Applications
Volume34
Issue number3
DOIs
StatePublished - 15 Nov 2013

Keywords

  • Doubling algorithm
  • M-matrix
  • Nonsymmetric algebraic Riccati equation
  • Numerically low-ranked solution

Fingerprint Dive into the research topics of 'Solving large-scale nonsymmetric algebraic riccati equations by doubling'. Together they form a unique fingerprint.

Cite this