Masters Theses
Date of Award
8-1981
Degree Type
Thesis
Degree Name
Master of Science
Major
Computer Science
Major Professor
Robert J. Plemmons
Committee Members
Terry Feagin, David Straight
Abstract
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.
Recommended Citation
Hume, David, "Ordering sparse least squares problems. " Master's Thesis, University of Tennessee, 1981.
https://trace.tennessee.edu/utk_gradthes/15197