Solving block low-rank linear systems by LU factorization is numerically stable
Solving block low-rank linear systems by LU factorization is numerically stable
复制标题
通过 LU 分解求解块低秩线性系统在数值上是稳定的
DOI：
--
复制
发表时间：
2021
影响因子：
2.1
通讯作者：
Théo Mary
中科院分区：
文献类型：
--
作者：
N. Higham;Théo Mary
块低秩（BLR）矩阵具有块低秩性质，可以用来降低数值线性代数算法的复杂度。这些低秩近似对浮点运算算法的数值稳定性的影响以前没有被分析过。我们提出了舍入误差分析的解决方案的线性系统的LU分解的BLR矩阵。假设一个稳定的枢转计划，我们证明向后稳定性：相对向后误差是有界的适度常数倍$varepsilon $，其中低秩阈值$varepsilon $是控制块低秩近似的精度的参数。除了这个关键的结果，我们的分析提供了三个新的见解BLR算法的数值行为。首先，我们比较了使用一个全球或当地的低秩阈值，并发现一个全球的首选。其次，我们表明，在因式分解过程中进行中间再压缩可以显着降低其成本，而不影响数值稳定性。第三，我们考虑不同的BLR因子分解变体，并确定更新压缩因子变体是最好的。对各种实际应用中的各种矩阵的测试表明，分析的预测在实践中得以实现。
Block low-rank (BLR) matrices possess a blockwise low-rank property that can be exploited to reduce the complexity of numerical linear algebra algorithms. The impact of these low-rank approximations on the numerical stability of the algorithms in floating-point arithmetic has not previously been analysed. We present rounding error analysis for the solution of a linear system by LU factorization of BLR matrices. Assuming that a stable pivoting scheme is used, we prove backward stability: the relative backward error is bounded by a modest constant times $varepsilon $, where the low-rank threshold $varepsilon $ is the parameter controlling the accuracy of the blockwise low-rank approximations. In addition to this key result, our analysis offers three new insights into the numerical behaviour of BLR algorithms. First, we compare the use of a global or local low-rank threshold and find that a global one should be preferred. Second, we show that performing intermediate recompressions during the factorization can significantly reduce its cost without compromising numerical stability. Third, we consider different BLR factorization variants and determine the update–compress–factor variant to be the best. Tests on a wide range of matrices from various real-life applications show that the predictions from the analysis are realized in practice.