Solving Large-Scale Nonsymmetric Algebraic Riccati Equations by Doubling

Tiexiang Li Southeast University ERIC KING-WAH CHU Monash University YUEH-CHENG KUO National University of Kaohsiung WEN-WEI LIN National Chiao Tung University

Numerical Analysis and Scientific Computing mathscidoc:1608.25001

Distinguished Paper Award in 2017

SIAM J Matrix Analysis and Applications, 34, (3), 2013
We consider the solution of the large-scale nonsymmetric algebraic Riccati equation XCX − XD − AX + B = 0, with M ≡ [D,−C;−B,A] ∈ R(n1+n2)×(n1+n2) being a nonsingular M-matrix. In addition, A and D are sparselike, with the products A−1u, A−⊤u, D−1v, and D−⊤v 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.
No keywords uploaded!
[ Download ] [ 2016-08-18 15:16:41 uploaded by litx ] [ 541 downloads ] [ 0 comments ]
@inproceedings{tiexiang2013solving,
  title={Solving Large-Scale Nonsymmetric Algebraic Riccati Equations by Doubling},
  author={Tiexiang Li, ERIC KING-WAH CHU, YUEH-CHENG KUO, and WEN-WEI LIN},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160818151641272584243},
  booktitle={SIAM J Matrix Analysis and Applications},
  volume={34},
  number={3},
  year={2013},
}
Tiexiang Li, ERIC KING-WAH CHU, YUEH-CHENG KUO, and WEN-WEI LIN. Solving Large-Scale Nonsymmetric Algebraic Riccati Equations by Doubling. 2013. Vol. 34. In SIAM J Matrix Analysis and Applications. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160818151641272584243.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved