Error bounds from extra-precise iterative refinement
Error bounds from extra-precise iterative refinement
复制标题
DOI：
10.1145/1141885.1141894
复制
发表时间：
2006-06
期刊：
影响因子：
--
通讯作者：
J. Demmel;Yozo Hida;W. Kahan;X. Li;Soni Mukherjee;E. J. Riedy
中科院分区：
文献类型：
--
作者：
J. Demmel;Yozo Hida;W. Kahan;X. Li;Soni Mukherjee;E. J. Riedy
我们提出了一种迭代求精线性方程组解的算法的设计和测试，在该算法中，以额外的精度计算残差。这个算法最初是在1948年提出的，并在20世纪60年代被分析为一种计算除最病态线性系统之外的所有线性系统的非常精确的解的方法。然而，到目前为止，有两个障碍阻碍了它在标准子例程库(如LAPACK)中的采用：(1)没有标准方法来访问计算残差所需的更高精度的算术；(2)如何为计算的解计算可靠的误差界尚不清楚。新的BLAS技术论坛标准的完成基本上消除了第一个障碍。为了克服第二个障碍，我们展示了如何使用迭代求精来以较小的代价计算任意范数的误差界，并用它来计算通常无穷范数的误差界和分量相对误差界。我们报告了对超过620万个5，10,100和1000维矩阵的广泛测试结果。只要算法计算的正态(分量)条件数小于1/ϵ{10，}ϵw，则计算的正态(分量)误差界最多为2max{10，}·ϵw，并且确实是真误差的界。这里，n是矩阵尺寸，ϵw=2−24是加工精度。残差以双精度(53位精度)计算。换句话说，对于大多数线性系统，该算法总是以可以忽略的额外成本计算出微小的误差。对于条件较差的问题(我们可以使用条件估计来检测)，我们在90%以上的情况下获得了小的正确误差界。
We present the design and testing of an algorithm for iterative refinement of the solution of linear equations where the residual is computed with extra precision. This algorithm was originally proposed in 1948 and analyzed in the 1960s as a means to compute very accurate solutions to all but the most ill-conditioned linear systems. However, two obstacles have until now prevented its adoption in standard subroutine libraries like LAPACK: (1) There was no standard way to access the higher precision arithmetic needed to compute residuals, and (2) it was unclear how to compute a reliable error bound for the computed solution. The completion of the new BLAS Technical Forum Standard has essentially removed the first obstacle. To overcome the second obstacle, we show how the application of iterative refinement can be used to compute an error bound in any norm at small cost and use this to compute both an error bound in the usual infinity norm, and a componentwise relative error bound.We report extensive test results on over 6.2 million matrices of dimensions 5, 10, 100, and 1000. As long as a normwise (componentwise) condition number computed by the algorithm is less than 1/max{10,}ϵw, the computed normwise (componentwise) error bound is at most 2 max{10, } · ϵw, and indeed bounds the true error. Here, n is the matrix dimension and ϵw = 2−24 is the working precision. Residuals were computed in double precision (53 bits of precision). In other words, the algorithm always computed a tiny error at negligible extra cost for most linear systems. For worse conditioned problems (which we can detect using condition estimation), we obtained small correct error bounds in over 90% of cases.