期刊
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
卷 37, 期 3, 页码 1279-1303出版社
SIAM PUBLICATIONS
DOI: 10.1137/15M1026195
关键词
hierarchical rank structure; backward stability; structured backward stability; error propagation; HSS algorithms; ULV factorization
资金
- NSF [DMS-1255416, DMS-1115572]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1255416] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据