SOLUTION OF SPARSE QUASI-SQUARE RECTANGULAR SYSTEMS BY GAUSSIAN-ELIMINATION

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.