Stability analysis of the two-level orthogonal Arnoldi procedure

Ding Lu; Yangfeng Su; Zhaojun Bai

doi:10.1137/151005142

Stability analysis of the two-level orthogonal Arnoldi procedure

Ding Lu, Yangfeng Su, Zhaojun Bai

Mathematics

Research output: Contribution to journal › Article › peer-review

40 Scopus citations

Abstract

The second-order Arnoldi (SOAR) procedure is an algorithm for computing an orthonormal basis of the second-order Krylov subspace. It has found applications in solving quadratic eigenvalue problems and model order reduction of second-order dynamical systems among others. Unfortunately, the SOAR procedure can be numerically unstable. The two-level orthogonal Arnoldi (TOAR) procedure has been proposed as an alternative to SOAR to cure the numerical instability. In this paper, we provide a rigorous stability analysis of the TOAR procedure. We prove that under mild assumptions, the TOAR procedure is backward stable in computing an orthonormal basis of the associated linear Krylov subspace. The benefit of the backward stability of TOAR is demonstrated by its high accuracy in structure-preserving model order reduction of second-order dynamical systems.

Original language	English
Pages (from-to)	195-214
Number of pages	20
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	37
Issue number	1
DOIs	https://doi.org/10.1137/151005142
State	Published - 2016

Bibliographical note

Funding Information:
School of Mathematical Sciences, Fudan University, Shanghai 200433, China (dinglu@fudan.edu.cn, yfsu@fudan.edu.cn). Part of this work was done while the first author was visiting the University of California, Davis, supported by China Scholarship Council. The research of the second author was supported in part by the Innovation Program of Shanghai Municipal Education Commission 13zz007, E-Institutes of Shanghai Municipal Education Commission N.E303004, and NSFC key project 91330201. ?Department of Computer Science and Department of Mathematics, University of California, Davis, CA 95616, USA (zbai@ucdavis.edu). The research of the this author was supported in part by the NSF grants DMS-1522697 and CCF-1527091.

Publisher Copyright:
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Keywords

Backward stability
Dynamical systems
Model order reduction
Second-order Arnoldi procedure
Second-order Krylov subspace

ASJC Scopus subject areas

Analysis

Access to Document

10.1137/151005142

Cite this

@article{066ffd236c4a4aae96902ea7371624d5,

title = "Stability analysis of the two-level orthogonal Arnoldi procedure",

abstract = "The second-order Arnoldi (SOAR) procedure is an algorithm for computing an orthonormal basis of the second-order Krylov subspace. It has found applications in solving quadratic eigenvalue problems and model order reduction of second-order dynamical systems among others. Unfortunately, the SOAR procedure can be numerically unstable. The two-level orthogonal Arnoldi (TOAR) procedure has been proposed as an alternative to SOAR to cure the numerical instability. In this paper, we provide a rigorous stability analysis of the TOAR procedure. We prove that under mild assumptions, the TOAR procedure is backward stable in computing an orthonormal basis of the associated linear Krylov subspace. The benefit of the backward stability of TOAR is demonstrated by its high accuracy in structure-preserving model order reduction of second-order dynamical systems.",

keywords = "Backward stability, Dynamical systems, Model order reduction, Second-order Arnoldi procedure, Second-order Krylov subspace",

author = "Ding Lu and Yangfeng Su and Zhaojun Bai",

note = "Funding Information: School of Mathematical Sciences, Fudan University, Shanghai 200433, China (dinglu@fudan.edu.cn, yfsu@fudan.edu.cn). Part of this work was done while the first author was visiting the University of California, Davis, supported by China Scholarship Council. The research of the second author was supported in part by the Innovation Program of Shanghai Municipal Education Commission 13zz007, E-Institutes of Shanghai Municipal Education Commission N.E303004, and NSFC key project 91330201. ?Department of Computer Science and Department of Mathematics, University of California, Davis, CA 95616, USA (zbai@ucdavis.edu). The research of the this author was supported in part by the NSF grants DMS-1522697 and CCF-1527091. Publisher Copyright: Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited.",

year = "2016",

doi = "10.1137/151005142",

language = "English",

volume = "37",

pages = "195--214",

number = "1",

}

TY - JOUR

T1 - Stability analysis of the two-level orthogonal Arnoldi procedure

AU - Lu, Ding

AU - Su, Yangfeng

AU - Bai, Zhaojun

N1 - Funding Information: School of Mathematical Sciences, Fudan University, Shanghai 200433, China (dinglu@fudan.edu.cn, yfsu@fudan.edu.cn). Part of this work was done while the first author was visiting the University of California, Davis, supported by China Scholarship Council. The research of the second author was supported in part by the Innovation Program of Shanghai Municipal Education Commission 13zz007, E-Institutes of Shanghai Municipal Education Commission N.E303004, and NSFC key project 91330201. ?Department of Computer Science and Department of Mathematics, University of California, Davis, CA 95616, USA (zbai@ucdavis.edu). The research of the this author was supported in part by the NSF grants DMS-1522697 and CCF-1527091. Publisher Copyright: Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PY - 2016

Y1 - 2016

N2 - The second-order Arnoldi (SOAR) procedure is an algorithm for computing an orthonormal basis of the second-order Krylov subspace. It has found applications in solving quadratic eigenvalue problems and model order reduction of second-order dynamical systems among others. Unfortunately, the SOAR procedure can be numerically unstable. The two-level orthogonal Arnoldi (TOAR) procedure has been proposed as an alternative to SOAR to cure the numerical instability. In this paper, we provide a rigorous stability analysis of the TOAR procedure. We prove that under mild assumptions, the TOAR procedure is backward stable in computing an orthonormal basis of the associated linear Krylov subspace. The benefit of the backward stability of TOAR is demonstrated by its high accuracy in structure-preserving model order reduction of second-order dynamical systems.

AB - The second-order Arnoldi (SOAR) procedure is an algorithm for computing an orthonormal basis of the second-order Krylov subspace. It has found applications in solving quadratic eigenvalue problems and model order reduction of second-order dynamical systems among others. Unfortunately, the SOAR procedure can be numerically unstable. The two-level orthogonal Arnoldi (TOAR) procedure has been proposed as an alternative to SOAR to cure the numerical instability. In this paper, we provide a rigorous stability analysis of the TOAR procedure. We prove that under mild assumptions, the TOAR procedure is backward stable in computing an orthonormal basis of the associated linear Krylov subspace. The benefit of the backward stability of TOAR is demonstrated by its high accuracy in structure-preserving model order reduction of second-order dynamical systems.

KW - Backward stability

KW - Dynamical systems

KW - Model order reduction

KW - Second-order Arnoldi procedure

KW - Second-order Krylov subspace

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

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

U2 - 10.1137/151005142

DO - 10.1137/151005142

M3 - Article

AN - SCOPUS:84962191169

VL - 37

SP - 195

EP - 214

IS - 1

ER -

Stability analysis of the two-level orthogonal Arnoldi procedure

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this