************************************************************************
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).
--------------------------------------------------------------------------------