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

Peter Chang Yi Weng, Hung-Yuan Fan, Eric King Wah Chu

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)729-740
Number of pages12
JournalApplied Mathematics and Computation
Volume219
Issue number2
DOIs
Publication statusPublished - 2012 Oct 1

Fingerprint

Nonsymmetric Algebraic Riccati Equation
Low-rank Approximation
Transport Theory
Riccati equations
Doubling
Sherman-Morrison Formula
Computational complexity
Diagonal matrix
M-matrix
Iterate
Data storage equipment
Computational Complexity
Update
Converge
Iteration
Numerical Examples
Requirements

Keywords

  • Doubling algorithm
  • Krylov subspace
  • M-matrix
  • Nonsymmetric algebraic Riccati equation

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this

Low-rank approximation to the solution of a nonsymmetric algebraic Riccati equation from transport theory. / Weng, Peter Chang Yi; Fan, Hung-Yuan; Chu, Eric King Wah.

In: Applied Mathematics and Computation, Vol. 219, No. 2, 01.10.2012, p. 729-740.

Research output: Contribution to journalArticle

@article{2083ba9f30584ebcb6a9ff3111e07725,
title = "Low-rank approximation to the solution of a nonsymmetric algebraic Riccati equation from transport theory",
abstract = "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.",
keywords = "Doubling algorithm, Krylov subspace, M-matrix, Nonsymmetric algebraic Riccati equation",
author = "Weng, {Peter Chang Yi} and Hung-Yuan Fan and Chu, {Eric King Wah}",
year = "2012",
month = "10",
day = "1",
doi = "10.1016/j.amc.2012.06.066",
language = "English",
volume = "219",
pages = "729--740",
journal = "Applied Mathematics and Computation",
issn = "0096-3003",
publisher = "Elsevier Inc.",
number = "2",

}

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

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

VL - 219

SP - 729

EP - 740

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

IS - 2

ER -