TY - JOUR

T1 - Low-rank approximation to the solution of a nonsymmetric algebraic Riccati equation from transport theory

AU - Weng, Peter Chang Yi

AU - Fan, Hung Yuan

AU - Chu, Eric King Wah

N1 - Funding Information:
This research work is partially supported by the National Science Council and the National Centre for Theoretical Sciences , Taiwan. The first author has been supported by a Monash Graduate Scholarship and a Monash International Postgraduate Research Scholarship . It is truly grateful from the second author that this research was partially supported by the National Science Council in Taiwan under Grant NSC 100-2115-M-003-004 . Part of the work was completed when the third author visited the National Centre for Theoretical Sciences at Tainan and the National Chiao Tung University, and we would like to thank these institutions.

PY - 2012/10/1

Y1 - 2012/10/1

N2 - We consider the solution of the large-scale nonsymmetric algebraic Riccati equation XCX-XD-AX+B=0 from transport theory (Juang 1995), with M≡[D,-C;-B,A]∈R2 n×2n being a nonsingular M-matrix. In addition, A,D are rank-1 updates of diagonal matrices, with the products A- 1u,A- ⊤u,D- 1v and D- ⊤v computable in O(n) complexity, for some vectors u and v, and B, C are rank 1. The structure-preserving doubling algorithm by Guo et al. (2006) 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, as illustrated by the numerical examples.

AB - We consider the solution of the large-scale nonsymmetric algebraic Riccati equation XCX-XD-AX+B=0 from transport theory (Juang 1995), with M≡[D,-C;-B,A]∈R2 n×2n being a nonsingular M-matrix. In addition, A,D are rank-1 updates of diagonal matrices, with the products A- 1u,A- ⊤u,D- 1v and D- ⊤v computable in O(n) complexity, for some vectors u and v, and B, C are rank 1. The structure-preserving doubling algorithm by Guo et al. (2006) 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, as illustrated by the numerical examples.

KW - Doubling algorithm

KW - Krylov subspace

KW - M-matrix

KW - Nonsymmetric algebraic Riccati equation

UR - http://www.scopus.com/inward/record.url?scp=84864983285&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864983285&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2012.06.066

DO - 10.1016/j.amc.2012.06.066

M3 - Article

AN - SCOPUS:84864983285

SN - 0096-3003

VL - 219

SP - 729

EP - 740

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 2

ER -