Extra-precise Iterative Refinement for Overdetermined Least Squares Problems

James Demmel and Yozo Hida and Xiaoye Li and Edward Jason Riedy

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-77

May 31, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-77.pdf

We present the algorithm, error bounds, and numerical results for extra-precise iterative refinement applied to overdetermined linear least squares (LLS) problems. We apply our linear system refinement algorithm to Bj&#246;rck's augmented linear system formulation of an LLS problem. Our algorithm reduces the forward normwise and componentwise errors to <i>O(&#949;)</i> unless the system is too ill conditioned. In contrast to linear systems, we provide two separate error bounds for the solution <i>x</i> and the residual <i>r</i>. The refinement algorithm requires only limited use of extra precision and adds only <i>O(m n)</i> work to the <i>O(m n<sup>2</sup>)</i> cost of QR factorization for problems of size <i>m</i>-by-<i>n</i>. The extra precision calculation is facilitated by the new extended-precision BLAS standard in a portable way, and the refinement algorithm will be included in a future release of LAPACK and can be extended to the other types of least squares problems.

BibTeX citation:

@techreport{Demmel:EECS-2007-77,
    Author= {Demmel, James and Hida, Yozo and Li, Xiaoye and Riedy, Edward Jason},
    Title= {Extra-precise Iterative Refinement for Overdetermined Least Squares Problems},
    Year= {2007},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-77.html},
    Number= {UCB/EECS-2007-77},
    Abstract= {We present the algorithm, error bounds, and numerical results for extra-precise iterative refinement applied to overdetermined linear least squares (LLS) problems. We apply our linear system refinement algorithm to Bj&#246;rck's augmented linear system formulation of an LLS problem. Our algorithm reduces the forward normwise and componentwise errors to <i>O(&#949;)</i> unless the system is too ill conditioned. In contrast to linear systems, we provide two separate error bounds for the solution <i>x</i> and the residual <i>r</i>. The refinement algorithm requires only limited use of extra precision and adds only <i>O(m n)</i> work to the <i>O(m n<sup>2</sup>)</i> cost of QR factorization for problems of size <i>m</i>-by-<i>n</i>. The extra precision calculation is facilitated by the new extended-precision BLAS standard in a portable way, and the refinement algorithm will be included in a future release of LAPACK and can be extended to the other types of least squares problems.},
}

EndNote citation:

%0 Report
%A Demmel, James 
%A Hida, Yozo 
%A Li, Xiaoye 
%A Riedy, Edward Jason 
%T Extra-precise Iterative Refinement for Overdetermined Least Squares Problems
%I EECS Department, University of California, Berkeley
%D 2007
%8 May 31
%@ UCB/EECS-2007-77
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-77.html
%F Demmel:EECS-2007-77