Symbolic Givens Reduction and Row-Ordering in Large Sparse Least Squares Problems

In the solution of large sparse least squares problems by Givens factorization, a preliminary symbolic step that determines a good processing order and a data structure for the matrix factor is used. In this paper, it is shown that a processing order equivalent to sequential processing by rows can be as good as any processing order using a single pivot row in each column. A notion of local acceptability in row-ordering is introduced and shown to reduce fill globally. Row-orderings satisfying this notion are essentially equivalent to sequential processing by rows and the nature of intermediate fill produced makes implicit representation of fill possible. This forms the basis for a symbolic Givens reduction algorithm that operates in a fixed data structure.