## 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^{-1}u, A^{-T}u, D^{-1}v, and D^{-T}v computable in O(n) complexity (with n = max{ n_{1}, n_{2}}), 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 language | English |
---|---|

Pages (from-to) | 1129-1147 |

Number of pages | 19 |

Journal | SIAM Journal on Matrix Analysis and Applications |

Volume | 34 |

Issue number | 3 |

DOIs | |

State | Published - 15 Nov 2013 |

## Keywords

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