James W. Demmel, Yozo Hida, William Kahan, Xiaoye S. Li, Soni Mukherjee and E. Jason Riedy

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1344
March 2005

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1344.pdf

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 the 1960s as a means to compute very accurate solutions to all but the most ill-conditioned linear systems of equations. 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 recently removed the first obstacle. To overcome the second obstacle, we show how a single 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 dimension 5, 10, 100, and 1000. As long as a normwise (resp. componentwise) condition number computed by the algorithm is less than 1/max{10, square root of n}epsilon-w, the computed normwise (resp. componentwise) error bound is at most 2 max{10, square root of n} * epsilon-w, and indeed bounds the true error. Here, n is the matrix dimension and epsilon-w = 2^-24 is single precision roundoff error. Residuals were computed in double precision (53 bits of precision). For worse conditioned problems, we get similarly small correct error bounds in over 89% of cases.

BibTeX citation:

@techreport{Demmel:CSD-04-1344,
    Author = {Demmel, James W. and Hida, Yozo and Kahan, William and Li, Xiaoye S. and Mukherjee, Soni and Riedy, E. Jason},
    Title = {Error Bounds from Extra Precise Iterative Refinement},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2005},
    Month = {Mar},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5919.html},
    Number = {UCB/CSD-04-1344},
    Abstract = {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 the 1960s as a means to compute very accurate solutions to all but the most ill-conditioned linear systems of equations. 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 recently removed the first obstacle. To overcome the second obstacle, we show how a single 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. <p> We report extensive test results on over 6.2 million matrices of dimension 5, 10, 100, and 1000. As long as a normwise (resp. componentwise) condition number computed by the algorithm is less than 1/max{10, square root of <i>n</i>}epsilon-w, the computed normwise (resp. componentwise) error bound is at most 2 max{10, square root of <i>n</i>} * epsilon-w, and indeed bounds the true error. Here, <i>n</i> is the matrix dimension and epsilon-w = 2^-24 is single precision roundoff error. Residuals were computed in double precision (53 bits of precision). For worse conditioned problems, we get similarly small correct error bounds in over 89% of cases.}
}

EndNote citation:

%0 Report
%A Demmel, James W.
%A Hida, Yozo
%A Kahan, William
%A Li, Xiaoye S.
%A Mukherjee, Soni
%A Riedy, E. Jason
%T Error Bounds from Extra Precise Iterative Refinement
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-04-1344
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5919.html
%F Demmel:CSD-04-1344