A new two-phase structure-preserving doubling algorithm for critically singular M-matrix algebraic Riccati equations

Tsung Ming Huang, Wei Qiang Huang, Ren Cang Li, Wen Wei Lin

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Summary: Among numerous iterative methods for solving the minimal nonnegative solution of an M-matrix algebraic Riccati equation, the structure-preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank-one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank-one component can be accurately recovered. We then propose an efficient hybrid method, called the two-phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two-phase SDA saves those SDA iterative steps that previously have to have for the rank-one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two-phase SDA. Copyright

Original languageEnglish
Pages (from-to)291-313
Number of pages23
JournalNumerical Linear Algebra with Applications
Volume23
Issue number2
DOIs
Publication statusPublished - 2016 Mar 1

Fingerprint

Algebraic Riccati Equation
Riccati equations
M-matrix
Phase structure
Doubling
Converge
Linearly
Iteration
Critical Case
Nonnegative Solution
Iterative methods
Hybrid Method
Convergence Analysis
Iterative Algorithm
Numerical Results
Approximation

Keywords

  • Critical case
  • M-matrix
  • M-matrix algebraic Riccati equation
  • Minimal nonnegative solution
  • Two-phase structure-preserving doubling algorithm

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics

Cite this

A new two-phase structure-preserving doubling algorithm for critically singular M-matrix algebraic Riccati equations. / Huang, Tsung Ming; Huang, Wei Qiang; Li, Ren Cang; Lin, Wen Wei.

In: Numerical Linear Algebra with Applications, Vol. 23, No. 2, 01.03.2016, p. 291-313.

Research output: Contribution to journalArticle

@article{006f64773fdf437f8e26a734f069e88e,
title = "A new two-phase structure-preserving doubling algorithm for critically singular M-matrix algebraic Riccati equations",
abstract = "Summary: Among numerous iterative methods for solving the minimal nonnegative solution of an M-matrix algebraic Riccati equation, the structure-preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank-one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank-one component can be accurately recovered. We then propose an efficient hybrid method, called the two-phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two-phase SDA saves those SDA iterative steps that previously have to have for the rank-one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two-phase SDA. Copyright",
keywords = "Critical case, M-matrix, M-matrix algebraic Riccati equation, Minimal nonnegative solution, Two-phase structure-preserving doubling algorithm",
author = "Huang, {Tsung Ming} and Huang, {Wei Qiang} and Li, {Ren Cang} and Lin, {Wen Wei}",
year = "2016",
month = "3",
day = "1",
doi = "10.1002/nla.2025",
language = "English",
volume = "23",
pages = "291--313",
journal = "Numerical Linear Algebra with Applications",
issn = "1070-5325",
publisher = "John Wiley and Sons Ltd",
number = "2",

}

TY - JOUR

T1 - A new two-phase structure-preserving doubling algorithm for critically singular M-matrix algebraic Riccati equations

AU - Huang, Tsung Ming

AU - Huang, Wei Qiang

AU - Li, Ren Cang

AU - Lin, Wen Wei

PY - 2016/3/1

Y1 - 2016/3/1

N2 - Summary: Among numerous iterative methods for solving the minimal nonnegative solution of an M-matrix algebraic Riccati equation, the structure-preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank-one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank-one component can be accurately recovered. We then propose an efficient hybrid method, called the two-phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two-phase SDA saves those SDA iterative steps that previously have to have for the rank-one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two-phase SDA. Copyright

AB - Summary: Among numerous iterative methods for solving the minimal nonnegative solution of an M-matrix algebraic Riccati equation, the structure-preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank-one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank-one component can be accurately recovered. We then propose an efficient hybrid method, called the two-phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two-phase SDA saves those SDA iterative steps that previously have to have for the rank-one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two-phase SDA. Copyright

KW - Critical case

KW - M-matrix

KW - M-matrix algebraic Riccati equation

KW - Minimal nonnegative solution

KW - Two-phase structure-preserving doubling algorithm

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

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

U2 - 10.1002/nla.2025

DO - 10.1002/nla.2025

M3 - Article

VL - 23

SP - 291

EP - 313

JO - Numerical Linear Algebra with Applications

JF - Numerical Linear Algebra with Applications

SN - 1070-5325

IS - 2

ER -