Algorithm 837: AMD, an approximate minimum degree ordering algorithm

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.

REFERENCES

• 1: Patrick R. Amestoy , Timothy A. Davis , Iain S. Duff, An Approximate Minimum Degree Ordering Algorithm, SIAM Journal on Matrix Analysis and Applications, v.17 n.4, p.886-905, Oct. 1996 [doi>10.1137/S0895479894278952]
• 2: Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004 [doi>10.1145/1024074.1024079]
• 3: A. George , W. H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review, v.31 n.1, p.1-19, Mar. 1989 [doi>10.1137/1031001]
• 4: Bruce Hendrickson , Edward Rothberg, Improving the Run Time and Quality of Nested Dissection Ordering, SIAM Journal on Scientific Computing, v.20 n.2, p.468-489, March 1998 [doi>10.1137/S1064827596300656]
• 5: HSL. 2002. HSL 2002: A collection of Fortran codes for large scale scientific computation. http://www.cse.clrc.ac.uk/nag/hsl.
• 6: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 7: 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.
• 8: Edward Rothberg , Stanley C. Eisenstat, Node Selection Strategies for Bottom-Up Sparse Matrix Ordering, SIAM Journal on Matrix Analysis and Applications, v.19 n.3, p.682-695, July 1998 [doi>10.1137/S0895479896302692]
• 9: Schulz, J. 2001. Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods. BIT 41, 4, 800--841.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Linear equations, minimum degree, ordering methods, sparse matrices