Row Ordering for a Sparse QR Decomposition

A new row ordering strategy based on pairing rows to minimize local fill-in is presented. The row ordering can be combined with most column ordering strategies to reduce computation, maintain sparsity, and solve rank deficient problems. Comparison of the new row pairing algorithm with Duff’s fixed pivot row ordering on a collection of sparse matrix test problems shows a median 47–71% reduction, depending on the column ordering, in floating point operations (flops) required for the QR decomposition. On a finite element application using nested domain decomposition for the column ordering, the new row ordering is competitive with the row ordering from nested domain decomposition.