Solution of sparse quasi-square rectangular systems by Gaussian elimination

We present a general method for the linear least-squares solutionof overdetermined and underdetermined systems. The method isparticularly efficient when the coefficient matrix is quasi-square,that is when the number of rows and number of columns is almostthe same. The numerical methods for linear least-squares problemsand minimum-norm solutions do not generally take account ofthis special characteristic. The proposed method is based onLU factorization of the original quasi-square matrix A, assumingthat A has full rank. In the overdetermined case, the LU factorsare used to compute a basis for the null space of A^T. The right-handside vector b is then projected onto this subspace and the least-squaressolution is obtained from the solution of this reduced problem.In the case of underdetermined systems, the desired solutionis again obtained through the solution of a reduced system.The use of this method may lead to important savings in computationaltime for both dense and sparse matrices. It is also shown inthe paper that, even in cases where the matrices are quite small,sparse solvers perform better than dense solvers. Some practicalexamples that illustrate the use of the method are included.