Sparse Gaussian elimination with partial pivoting computes the factorization
PAQ= LUof a sparse matrix A, where the row ordering Pis selected during factorization using standard partial pivoting with row interchanges. The goal is to select a column preordering, Q, based solely on the nonzero pattern of A, that limits the worst-case number of nonzeros in the factorization. The fill-in also depends on P, but Qis selected to reduce an upper bound on the fill-in for any subsequent choice of P. The choice of Qcan have a dramatic impact on the number of nonzeros in Land U. One scheme for determining a good column ordering for Ais to compute a symmetric ordering that reduces fill-in in the Cholesky factorization of A T A. A conventional minimum degree ordering algorithm would require the sparsity structure of A T Ato be computed, which can be expensive both in terms of space and time since A T Amay be much denser than A. An alternative is to compute Qdirectly from the sparsity structure of A; this strategy is used by MATLAB's COLMMD preordering algorithm. A new ordering algorithm, COLAMD, is presented. It is based on the same strategy but uses a better ordering heuristic. COLAMD is faster and computes better orderings, with fewer nonzeros in the factors of the matrix.