Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems

Reviewer: Jesse Louis Barlow

The algorithm for iterative refinement of least squares given here is an update of the 1967 work of Bj?rck [1], with more recent ideas about componentwise errors and condition estimation. These ideas influenced stopping criteria, the use of the Hager-Higham condition estimator [2,3] to estimate relevant conditioning parameters, and the discussion of the role of extra-precision. Iterative refinement cannot be expected to improve the solutions of problems that are ill-conditioned, but can provide significant improvement for non-ill-conditioned problems, which are called "acceptably conditioned" here. The authors state two goals for the refinement algorithm: "for acceptably conditioned problems [to] obtain small errors," and that "a small error bound returned from the code [be] trustworthy." One new theorem is proven, but it is similar to bounds that have appeared in previous work by some of the authors [4]; the new results of the paper are about the numerical tests of the software. The authors do one million test problems, of which 577,412 are acceptably conditioned by standard normwise measures. All but 35 of these problems converged according to their stopping criteria, and for those the condition number in the infinity norm is larger than or close to the condition threshold. Thus, they could arguably be put in the ill-conditioned category. For the convergent problems, the algorithm delivered tiny errors for the solution and least squares residuals, both normwise and componentwise-so the first goal was achieved. The second goal was also achieved for the acceptably conditioned problems-they were close to actual error and did not underestimate true errors. The software described is useful for providing the best solution that can be reasonably expected to acceptably conditioned least squares problems. Online Computing Reviews Service