back to Tim Davis' home page

The Approximate Minimum Degree ordering algorithm (AMD/MC47):

AMD appears as MC47 in Release 12 of the Harwell Subroutine Library. Related AMD variants (not AMD itself, however) are available for non-commercial use in NETLIB and also available below. Take a look at my technical report lists for more information. For papers related to the talk, see TR-94-039 "An approximate minimum degree ordering algorithm" (SIAM J. Matrix Analysis and Applications, vol. 17, no. 4, (1996), pp. 886-905), TR-97-016 "A combined unifrontal/multifrontal method for unsymmetric sparse matrices." (to appear in ACM TOMS). and TR-94-038 "An unsymmetric-pattern multifrontal method for sparse LU factorization" (SIAM J. Matrix Analysis and Applications, vol. 18, no. 1, (1997), pp. 140-158).

Changes:

• AMDPRE was added on May 1, 1997. It removes dense rows/columns from the matrix prior to ordering the matrix via AMDBAR. It can be much faster than AMDBAR when the matrix has one or more dense rows/columns.
• Matlab interface added on August 6, 1998. To use AMDBAR in Matlab, you'll need amdbarmex.f, amdbar.m, amdbar.f, and amdbar_demo.m. These files have been submitted to Netlib, and should appear in http://www.netlib.org/linalg/amd/.

Notice:

If you are not in academia then you CANNOT use the AMD variants, except for benchmarking. For a commericial copy of MC47, in the Harwell Subroutine Library, contact : Pascale Hicklin, Tel:+44 (0)1235 448330, Fax: +44 (0)1235 448350, e-mail: hsl@hyprotech.com, Web site: www.hsl-library.com, Hyprotech UK Ltd, A subsidiary of Aspen Technology, Inc., Gemini Building, Fermi Avenue, Harwell International Business Centre, Didcot, Oxfordshire OX11 0QR, UK, www.hyprotech.com. who will provide details of price and conditions of use. AMD and MC47 are COPYRIGHTED SOFTWARE.

AMD files:

• linalg/amd/readme : readme for approximate minimum degree ordering routines
• linalg/amd/amdatr.f : approximate minimum degree ordering of a sparse symmetric matrix (upper bound on true degree).
• linalg/amd/amdbar.f : approximate minimum degree ordering of a sparse symmetric matrix (upper bound on external degree).
• linalg/amd/amdexa.f : approximate minimum degree ordering of a sparse symmetric matrix (exact external degree).
• linalg/amd/amdhaf.f : approximate minimum degree ordering of a sparse symmetric matrix ("half-and-half" degree).
• linalg/amd/amdhat.f : approximate minimum degree ordering of a sparse symmetric matrix (Gilbert, Moler, and Schreiber bound on external degree).
• linalg/amd/amdtru.f : approximate minimum degree ordering of a sparse symmetric matrix (exact true degree).
• linalg/amd/amdpre.f : Preordering for AMDBAR (removes dense rows and columns).
• amdbar.m : Matlab interface for AMDBAR. You also need amdbar_demo.m and amdbarmex.f.
• amdbarmex.f : Matlab interface for AMDBAR.
• amdbar_demo.m : Demo for the Matlab interface to AMDBAR.