On Row and Column Orderings for Sparse Least Squares Problems

Let P₁ and P₂ be respectively m × m and n × n permutation matrices, with m n. Suppose the m × n sparse matrix A = P₁ AP₂ is reduced to upper trapezoidal form [ array*20c R \\ 0 \\ array ] through the application of Givens rotations sequentially to the rows of A. It is well known that the sparsity of R depends only on the choice of P₂, but the choice of P₁ can drastically affect the arithmetic required to compute R. In this paper we provide a mechanism for studying the connection between good row and good column orderings, along with a modified nested dissection algorithm for finding a good P₂ which automatically induces a good P₁. An analysis for a model problem is given, along with some experimental results.