On the stability of some hierarchical rank structured matrix algorithms

Yuanzhe Xi, Jianlin Xia

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

In this paper, we investigate the numerical error propagation and provide systematic backward stability analysis for some hierarchical rank structured matrix algorithms. We prove the backward stability of various important hierarchically semiseparable (HSS) methods, such as HSS matrix-vector multiplications, HSS ULV linear system solutions, HSS linear least squares solutions, HSS inversions, and some variations. Concrete backward error bounds are given, including a structured backward error for the solution in terms of the structured factors. The error propagation factors involve only low-degree powers of the maximum off-diagonal numerical rank and the logarithm of the matrix size. Thus, as compared with the corresponding standard dense matrix algorithms, the HSS algorithms not only are faster but also have much better stability. We also show that factorization-based HSS solutions are usually preferred, while inversion-based ones may suffer from numerical instability. The analysis builds a comprehensive framework for understanding the backward stability of hierarchical rank structured methods. The error propagation patterns also provide insights into the improvement of other types of structured solvers and the design of new stable hierarchical structured algorithms. Some numerical examples are included to support the studies.

Original languageEnglish (US)
Pages (from-to)1279-1303
Number of pages25
JournalSIAM Journal on Matrix Analysis and Applications
Volume37
Issue number3
DOIs
StatePublished - 2016

Bibliographical note

Funding Information:
The work of the second author was supported in part by NSF CAREER Award DMS-1255416 and NSF grant DMS-1115572.

Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.

Keywords

  • Backward stability
  • Error propagation
  • HSS algorithms
  • Hierarchical rank structure
  • Structured backward stability
  • ULV factorization

Fingerprint

Dive into the research topics of 'On the stability of some hierarchical rank structured matrix algorithms'. Together they form a unique fingerprint.

Cite this