On the Failure of Rank-Revealing QR Factorization Software -- A Case Study
On the Failure of Rank-Revealing QR Factorization Software -- A Case Study
复制标题
论显示排名的 QR 分解软件的失败——一个案例研究
DOI：
10.1145/1377612.1377616
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Zvonimir Bujanovic
中科院分区：
文献类型：
--
作者：
Z. Drmač;Zvonimir Bujanovic
本文报告了LAPACK软件实现的带有Businger-Golub列旋转的QR因式分解的意外且相当反复无常的行为。结果表明，由于有限精度的算法，分解的软件实现可能灾难性地不能产生结构合理的三角因子，从而导致对矩阵的数值秩有潜在的严重低估。这个有30年历史的问题可以追溯到Linpack，已经(不知不觉地)严重影响了许多计算例程和软件包，以及揭示排名的QR因式分解的研究。我们将计算机实验和数值分析相结合来隔离、分析和解决问题。我们对当前LAPACK xGEQP3例程的修改已经包含在LAPACK 3.1.0版本中。修改后的例程在数值上更加健壮，并且开销可以忽略不计。我们还提供了一种新的、同样有效并且在数值上被证明是安全的部分列范数更新策略。
This article reports an unexpected and rather erratic behavior of the LAPACK software implementation of the QR factorization with Businger-Golub column pivoting. It is shown that, due to finite precision arithmetic, the software implementation of the factorization can catastrophically fail to produce a properly structured triangular factor, thus leading to a potentially severe underestimate of a matrix's numerical rank. The 30-year old problem, dating back to LINPACK, has (undetectedly) badly affected many computational routines and software packages, as well as the study of rank-revealing QR factorizations. We combine computer experiments and numerical analysis to isolate, analyze, and fix the problem. Our modification of the current LAPACK xGEQP3 routine is already included in the LAPACK 3.1.0 release. The modified routine is numerically more robust and with a negligible overhead. We also provide a new, equally efficient, and provably numerically safe partial-column norm-updating strategy.
影响因子：
2.1
作者：
通讯作者：
--