Return to Colloquia & Seminar listing
Extra-precise Iterative Refinement for Least Squares Problems
Applied Math| Speaker: | Xiaoye S Li, Lawrence Berkeley National Laboratory |
| Location: | 1147 MSB |
| Start time: | Fri, Apr 13 2007, 12:10PM |
Description
We present the algorithm, error bounds, and numerical results
of the extra-precise iterative refinement for overdetermined linear least
squares (LLS) problems. We apply our linear system refinement algorithm
to Bjorck's augmented linear system formulation of an LLS problem.
Our algorithm reduces the forward normwise and componentwise errors
to O(macheps) unless the system is too ill-conditioned.
In contrast to linear systems, we provide two separate error bounds
for the solution X and the residual R.
The refinement algorithm requires only limited use of extra
precision and adds only O(m*n) work to the O(m*n^2) cost of QR factorization
for problems of size m-by-n.
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.
Joint work with Jim Demmel, Yozo Hida, and Jason Riedy