Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm Academic Article uri icon

abstract

  • Two codes are discussed, COLAMD and SYMAMD, that compute approximate minimum degree orderings for sparse matrices in two contexts: (1) sparse partial pivoting, which requires a sparsity preserving column pre-ordering prior to numerical factorization, and (2) sparse Cholesky factorization, which requires a symmetric permutation of both the rows and columns of the matrix being factorized. These orderings are computed by COLAMD and SYMAMD, respectively. The ordering from COLAMD is also suitable for sparse QR factorization, and the factorization of matrices of the form A T A and AA T , such as those that arise in least-squares problems and interior point methods for linear programming problems. The two routines are available both in MATLAB and C-callable forms. They appear as built-in routines in MATLAB Version 6.0.

published proceedings

  • ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE

author list (cited authors)

  • Davis, T. A., Gilbert, J. R., Larimore, S. I., & Ng, E. G.

complete list of authors

  • Davis, TA||Gilbert, JR||Larimore, SI||Ng, EG