|
Abstract : |
For sparse QR factorization, finding a good column ordering of the matrix to be factorized, is essential. Both the amount of fill in the resulting factors, and the number of floating-point operations required by the factorization, are highly dependent on this ordering. A suitable column ordering of the matrix A is usually obtained by minimum degree analysis on A T A. The objective of this analysis is to produce low fill in the resulting triangular factor R. We observe that the efficiency of sparse QR factorization is also dependent on other criteria, like the size and the structure of intermediate fill, and the size and the structure of the frontal matrices for the multifrontal method, in addition to the amount of fill in R. An important part of this information is lost when A T A is formed. However, the structural information from A is important to consider in order to find good column orderings. We show how a suitable equivalent reordering of an initial fill-reducing ordering can decrease the number of operations required by multifrontal QR factorization, without increasing the number of nonzeros in R. Heuristics that produce good equivalent reorderings are proposed and explained. We also propose tie-breaking strategies for the minimum degree algorithm, which produce orderings that require considerably less number of operations in both multifrontal and traditional Householder QR factorization, than the standard minimum degree algorithm without tie-breaking., |
