J. Cardenal et al., SOLUTION OF SPARSE QUASI-SQUARE RECTANGULAR SYSTEMS BY GAUSSIAN-ELIMINATION, IMA journal of numerical analysis, 18(2), 1998, pp. 165-177
We present a general method for the linear least-squares solution of o
verdetermined and underdetermined systems. The method is particularly
efficient when the coefficient matrix is quasi-square, that is when th
e number of rows and number of columns is almost the same. The numeric
al methods for linear least-squares problems and minimum-norm solution
s do not generally take account of this special characteristic. The pr
oposed method is based on an LU factorization of the original quasi-sq
uare matrix A, assuming that A has full rank. In the overdetermined ca
se, the LU factors are used to compute a basis for the null space of A
(T). The right-hand side vector b is then projected onto this subspace
and the least-squares solution is obtained from the solution of this
reduced problem. In the case of underdetermined systems, the desired s
olution is again obtained through the solution of a reduced system. Th
e use of this method may lead to important savings in computational ti
me for both dense and sparse matrices. It is also shown in the paper t
hat, even in cases where the matrices are quite small, sparse solvers
perform better than dense solvers. Some practical examples that illust
rate the use of the method are included.