Ordering sparse least squares problems

Relative performances of three methods for ordering a large sparse least squares problem Ax = b, where A is m x n, m ≥ n, and of rank n, are compared. A system Ax = b is ordered by finding permutation matrices P and Q so that the equivalent reordered system PAQ = Pb suffers little fill-in when forming its Cholesky factor. An ordering method attempts to exploit the sparsity of A by reducing fill-in, operation counts, and execution time required for solving the system Ax = b. The system Ax = b is ordered by minimum degree ordering, nested dissection, and block trapezoidal ordering prior to its solution using Givens reduction to compute the Cholesky factor.

Software for implementing the ordering methods is based upon a version of SPARSPAK, a package of sparse matrix routines, modified by George and Heath to implement the Givens reduction process. of Duff, Reid, and Litsey are used to implement block trapezoidal ordering. Results obtained from test problems show that all three ordering methods greatly reduce fill-in, operation counts, and factorization times for solving Ax = b. In the case of an 892 × 261 problem, fill-in, operation counts, and factorization times were reduced 85% to 90% from the amounts required when the problem is solved without any ordering.