AMD: approximate minimum degree ordering

AMD is a set of routines for ordering a sparse matrix prior to Cholesky factorization (or for LU factorization with diagonal pivoting). There are versions in both C and Fortran. A MATLAB interface is provided. Note that this software has nothing to do with AMD the company. This package runs on any platform.

Copyright, and License:

Copyright (c) 2004-2012 by Timothy A. Davis, Patrick R. Amestoy, and Iain S. Duff. All Rights Reserved. Distributed under the GNU LGPL license.

Availability:

• Download the current version of AMD itself here.
• Browse the source code.
• Requires the SuiteSparse_config package.
• Get all of SuiteSparse here.

Contributions, and related codes:

• The 6 variants discussed in our SIMAX paper on AMD, in Fortran
• AMD is the default preordering used in MA41, by Patrick Amestoy, Iain Duff, and Chiara Puglisi.
• COLAMD is the default preordering used in SuperLU, by Sherry Li (Lawrence Berkeley National Lab).
• AMD is one of the orderings in UMFPACK.
• AMD was originally based on the MA27 minimum degree ordering algorithm, by Iain Duff and John Reid, in the HSL library.
• The AMD algorithm is the default ordering method in CPLEX. It is up to 30 times faster than alternative minimum degree ordering methods when used in CPLEX.

Versions (Unix/Linix):

• AMD-2.3.1.tar.gz (current version)
• AMD-2.3.0.tar.gz
• AMD-2.2.4.tar.gz
• AMD-2.2.3.tar.gz
• AMD-2.2.2.tar.gz
• AMD-2.2.1.tar.gz
• AMD-2.2.0.tar.gz
• AMD-2.0.4.tar.gz
• AMD-2.0.3.tar.gz
• AMD-2.0.1.tar.gz
• AMD-2.0.0.tar.gz
• AMD-1.2.0.tar.gz
• AMD-1.1.0.tar.gz

References (please cite these when using this software):

• Algorithm 837: AMD, An approximate minimum degree ordering algorithm, P. Amestoy, T. A. Davis, and I. S. Duff, ACM Transactions on Mathematical Software, vol 30, no. 3, Sept. 2004, pp. 381-388.
• An approximate minimum degree ordering algorithm, P. Amestoy, T. A. Davis, and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, vol 17, no. 4, pp. 886-905, Dec. 1996.
• Direct Methods for Sparse Linear Systems, T. A. Davis, SIAM, Philadelphia, Sept. 2006. Part of the SIAM Book Series on the Fundamentals of Algorithms.