Algorithm 853
Leslie V. Foster, Rajesh K. Kommu · ACM Transactions on Mathematical Software · 2006
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 n 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.