Algorithm 836
- 1 September 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 30 (3) , 377-380
- https://doi.org/10.1145/1024074.1024080
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.Keywords
This publication has 6 references indexed in Scilit:
- A column approximate minimum degree ordering algorithmACM Transactions on Mathematical Software, 2004
- MATLAB Primer, Sixth EditionPublished by Taylor & Francis ,2001
- A Supernodal Approach to Sparse Partial PivotingSIAM Journal on Matrix Analysis and Applications, 1999
- An Approximate Minimum Degree Ordering AlgorithmSIAM Journal on Matrix Analysis and Applications, 1996
- Sparse Matrices in MATLAB: Design and ImplementationSIAM Journal on Matrix Analysis and Applications, 1992
- Sparse Partial Pivoting in Time Proportional to Arithmetic OperationsSIAM Journal on Scientific and Statistical Computing, 1988