On the Stability of Some Hierarchical Rank Structured Matrix Algorithms
On the Stability of Some Hierarchical Rank Structured Matrix Algorithms
复制标题
几种层次秩结构矩阵算法的稳定性研究
DOI：
10.1137/15m1026195
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Xia
中科院分区：
文献类型：
--
作者：
Yuanzhe Xi;J. Xia
本文研究了几种层次秩结构矩阵算法的数值误差传播，并给出了系统的后向稳定性分析。我们证明了向后稳定的各种重要的分层半可分（HSS）的方法，如HSS矩阵向量乘法，HSS ULV线性系统的解决方案，HSS线性最小二乘解决方案，HSS反演，和一些变化。给出了具体的向后误差界，包括结构化因子的解的结构化向后误差。误差传播因子仅涉及最大非对角数值秩的低次幂和矩阵大小的对数。因此，与相应的标准稠密矩阵算法相比，HSS算法不仅速度更快，而且具有更好的稳定性。我们还表明，基于因子分解的HSS解决方案通常是首选的，而基于反演的可能会遭受数值不稳定性。该分析建立了一个全面的F…
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 f...
影响因子：
2.1
作者：
通讯作者：
--