Patrick R. Amestoy
Timothy A. Davis
Abstract
AMD is a set of routines that implements the approximate minimum degree ordering algorithm to permute sparse matrices prior to numerical factorization. There are versions written in both C and Fortran 77. A MATLAB interface is included.
Supplemental Material
Available for Download
Software for "AMD, an approximate minimum degree ordering algorithm"
- Amestoy, P. R., Davis, T. A., and Duff, I. S. 1996. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Applic. 17, 4, 886--905. Google Scholar
Digital Library
- Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. G. 2004. A column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3 (Sept.), 000--000. Google ScholarDigital Library
- George, A. and Liu, J. W. H. 1989. The evolution of the minimum degree ordering algorithm. SIAM Rev. 31, 1, 1--19. Google ScholarDigital Library
- Hendrickson, B. and Rothberg, E. 1999. Improving the runtime and quality of nested dissection ordering. SIAM J. Sci. Comput. 20, 468--489. Google ScholarDigital Library
- HSL. 2002. HSL 2002: A collection of Fortran codes for large scale scientific computation. http://www.cse.clrc.ac.uk/nag/hsl.Google Scholar
- Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359--392. Google ScholarDigital Library
- Pellegrini, F., Roman, J., and Amestoy, P. 2000. Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering. Concurrency: Practice and Experience 12, 68--84.Google Scholar
- Rothberg, E. and Eisenstat, S. C. 1998. Node selection strategies for bottom-up sparse matrix orderings. SIAM J. Matrix Anal. Applic. 19, 3, 682--695. Google ScholarDigital Library
- Schulz, J. 2001. Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods. BIT 41, 4, 800--841.Google ScholarCross Ref
Index Terms
- Algorithm 837: AMD, an approximate minimum degree ordering algorithm
Recommendations
A column approximate minimum degree ordering algorithm
Sparse Gaussian elimination with partial pivoting computes the factorization PAQ = LU of a sparse matrix A, where the row ordering P is selected during factorization using standard partial pivoting with row interchanges. The goal is to select a column ...
Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm
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, ...
Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate
CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, ...
Reviews
Peter C. Patton
Algorithm 837, called AMD, is a set of routines in C and FORTRAN 77 for preordering a sparse matrix prior to numerical factorization. It finds a permutation matrix, P , for the Cholesky factorization of a matrix, A , into its factors, L and L T ; that is, PAP T = LL T . The point is to do the factorization with less zeros than a straight Cholesky factorization of A , and this solution is much faster than other methods. It does not try to find the minimum degree ordering, but is satisfied to find the approximate minimum degree, in the interest of time. Rather than keep track of the exact degree of the ordering, the algorithm finds an upper bound on the degree that is easier (and faster) to compute. To call the algorithm from MATLAB, one simply writes p=amd(A) to find the permutation vector p , and then calls the Cholesky factorization with chol(A(p,p)) . In C, the C-callable AMD library consists of five user-callable routines and an included file ( #include "amd.h" ). Two FORTRAN versions are provided, but, unlike the C version, they require a symmetric nonzero pattern in A , with no diagonal entries present. This is a clearly written paper that explains everything the prospective user of Algorithm 837 needs to know. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments