Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems Export

@article{citeulike:5023630, 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\örck\’s augmented linear system formulation of an LLS problem. Our algorithm reduces the forward normwise and componentwise errors to O ( \ϵ w ), where \ϵ w is the working precision, 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 ( mn ) work to the O ( mn 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.}, address = {New York, NY, USA}, author = {Demmel, James and Hida, Yozo and Riedy, E. Jason and Li, Xiaoye S.}, citeulike-article-id = {5023630}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1462177}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1462173.1462177}, doi = {10.1145/1462173.1462177}, issn = {0098-3500}, journal = {ACM Trans. Math. Softw.}, keywords = {error\_analysis, floating\_point, high-performance\_computing, linear\_algebra, mixed\_precision}, number = {4}, pages = {1--32}, posted-at = {2009-06-30 16:35:01}, priority = {2}, publisher = {ACM}, title = {Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems}, url = {http://dx.doi.org/10.1145/1462173.1462177}, volume = {35}, year = {2009} }

TY - JOUR ID - citeulike:5023630 L3 - citeulike-article-id:5023630 N2 - 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örck’s augmented linear system formulation of an LLS problem. Our algorithm reduces the forward normwise and componentwise errors to O ( ϵ w ), where ϵ w is the working precision, 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 ( mn ) work to the O ( mn 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. IS - 4 JF - ACM Trans. Math. Softw. SN - 0098-3500 AD - New York, NY, USA EP - 32 TI - Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems PB - ACM VL - 35 SP - 1 KW - error_analysis KW - floating_point KW - high-performance_computing KW - linear_algebra KW - mixed_precision AU - Demmel, James AU - Hida, Yozo AU - Riedy, Jason AU - Li, Xiaoye PY - 2009/// UR - http://dx.doi.org/10.1145/1462173.1462177 ER -