************************************************************************ Approximate Minimum Degree Ordering Algorithm (and related variants) ************************************************************************ AUTHORS (and Copyright 1995 (C) by): Timothy A. Davis, Patrick Amestoy, Iain S. Duff, and John K. Reid. Changes: AMDPRE added on May 1, 1997. SUMMARY: The six AMD routines in this package compute a minimum degree ordering of a sparse symmetric matrix. For details on the methods used, see "An approximate minimum degree ordering algorithm," SIAM J. Matrix Analysis and Applications (to appear), by Amestoy, Davis, and Duff. Also see the technical report of the same name, TR-94-039, CISE Dept, Univ. of Florida (available via anonymous ftp to ftp.cise.ufl.edu, or via the WWW at http://www.cise.ufl.edu/~davis). ************************************************************************ * NOTICE: "The AMD routines (AMDEXA, AMDBAR, AMDHAF, AMDHAT, AMDTRU, * and AMDATR) may be used SOLELY for educational, research, and * benchmarking purposes by non-profit organizations and the U.S. * government. Commercial and other organizations may make use of the * AMD routines SOLELY for benchmarking purposes only. The AMD * routines may be modified by or on behalf of the User for such * use but at no time shall the AMD routines or any such modified * version of them become the property of the User. The AMD routines * are provided without warranty of any kind, either expressed or * implied. Neither the Authors nor their employers shall be liable * for any direct or consequential loss or damage whatsoever arising * out of the use or misuse of the AMD routines by the User. The AMD * routines must not be sold. You may make copies of the AMD routines, * but this NOTICE and the Copyright notice must appear in all copies. * Any other use of the AMD routines requires written permission. * Your use of the AMD routines is an implicit agreement to these * conditions." ************************************************************************ The routines differ only by what type of degree (or approximation) is used to select the pivots. These six routines correspond to the six variants discussed in Section 6.2 of the paper mentioned above. Routine Degree ------- ------ AMDEXA d: the exact external degree (as used in MMD, for example). AMDBAR d_bar: our upper bound on the external degree. This is nearly always superior (or at least comparable) to the other five AMD routines, in terms of ordering quality, run time, or both. AMDHAF d_tilde: "half-and-half", suggested by Lucas, Ashcraft, and Eisenstat. Uses d when a variable is adjacent to two elements, d_hat otherwise. AMDHAT d_hat: Gilbert, Moler, and Schreiber's bound on the external degree (as used in MATLAB). AMDTRU t: the exact true degree (as used in MA27, for example). AMDATR t_bar: our upper bound on the true degree. AMDPRE same as AMDBAR, except that it first removes "dense" nodes from the graph (ordering them last). Can be a lot faster than AMDBAR, for matrices with dense rows and columns. Added to the AMD* suite on May 1, 1997. This preprocessing step is described in the accompanying tech report, amdpre.ps. To look at the differences in the code in the six routines, you may wish to try the following pairwise comparisons (using the Unix "diff" command, for example): diff amdexa.f amdtru.f Exact external vs. exact true degree. Nearly identical. Note that the exact external degree excludes NVI, the number of variables/nodes in supervariable/supernode I. diff amdbar.f amdatr.f Approximate external vs. approx true degree. Also nearly identical code. diff amdbar.f amdexa.f Approximate external vs. exact external. This is the most important comparison. The most computationally intensive code in AMDEXA is the innermost loop, DO 145. Note that it does not appear in AMDBAR, being replaced with a single statement (DEG = DEG + WE - WFLG). There is an additional loop (DO 150) in AMDBAR *not* in AMDEXA that has a lower time complexity as the AMDBAR outer loop (DO 180). These changes are why AMDBAR is much faster than AMDEXA. diff amdbar.f amdhat.f Approx external vs. MATLAB degree. These two codes are very similar, except that AMDHAT does not require the DO 150 loop, or another rarely executed loop (DO 190) that resets a work vector. The degree computation code (DO 180) is identical except for one line that sums up the contributions to the degree (DEG = DEG + ...). This is why the run time of the two codes is similar. The ordering quality is very different, however (AMDBAR is typically much better than AMDHAT in terms of ordering quality). diff amdhaf.f amdhat.f Half-and-half degree vs. MATLAB degree. The half-and-half degree computes either the MATLAB degree or the exact external degree. Only when a variable/node is adjacent to two elements/cliques does AMDHAF compute the exact external degree. diff amdhaf.f amdexa.f half-and-half degree vs. exact external. AMDHAF and AMDEXA both include code that computes the exact external degree (DO 145, which is the same in both except for the indentation). The AMDBAR routine is similar to the MC47B/BD routine that will appear in the next release of the Harwell Subroutine Library. No error checking of input arguments is done by any AMD routine. The MC47A/AD routine in the Harwell Subroutine Library provides a simpler user interface, checks for errors, and then calls MC47B/BD to perform the ordering. MC47B/BD also includes aggressive element absorption which can improve the quality of the ordering and reduce the time to compute the ordering (not used in the AMD routines). The MC47 package is available for commercial use. Technical reports, information on HSL, and matrices are available via the World Wide Web at http://www.cis.rl.ac.uk/struct/ARCD/NUM.html, or by anonymous ftp at seamus.cc.rl.ac.uk/pub. Also contact John Harding, Harwell Subroutine Library, B 552, AEA Technology, Harwell, Didcot, Oxon OX11 0RA, England. telephone (44) 1235 434573, fax (44) 1235 434340, email john.harding@aeat.co.uk, who will provide details of price and conditions of use. A final note ... these six routines have been extensively tested (no warranty implied or otherwise, however!). None of them check the input arguments for errors, however. If the codes are given incorrect input, they usually CRASH, or at best return an invalid permutation. Thus, if you experience difficulty with these routines, it is nearly certainly an error in the input arguments. If a failure occurs, check your inputs carefully before assuming that there is a bug in the AMD routines. Better yet, obtain the MC47 package, which includes extensive error checking of the user's input arguments. Submitted to NETLIB on January 18, 1996 by Tim Davis (davis@cise.ufl.edu). This work was supported by the National Science Foundation (ASC-9111263 and DMS-9223088). --------------------------------------------------------------------------------