Algorithm 853: An Efficient Algorithm for Solving Rank-Deficient Least Squares Problems

摘要

Existing routines, such as xGELSY or xGELSD in LAPACK, for solving rank-deficient least squares problems require O(mn~2) operations to solve min ‖b - Ax ‖ where A is an m by re matrix. We present a modification of the LAPACK routine xGELSY that requires O(mnk) operations where k is the effective numerical rank of the matrix A. For low rank matrices the modification is an order of magnitude faster than the LAPACK code.