An approximate minimum degree ordering algorithm Academic Article

abstract

• An approximate minimum degree (AMD) ordering algorithm for preordering a symmetric sparse matrix prior to numerical factorization is presented. We use techniques based on the quotient graph for matrix factorization that allow us to obtain computationally cheap bounds for the minimum degree. We show that these bounds are often equal to the actual degree. The resulting algorithm is typically much faster than previous minimum degree ordering algorithms and produces results that are comparable in quality with the best orderings from other minimum degree algorithms.

authors

• Davis, Timothy

published proceedings

• SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS

author list (cited authors)

• Amestoy, P. R., Davis, T. A., & Duff, I. S.

citation count

• 431

complete list of authors

• Amestoy, PR||Davis, TA||Duff, IS

publication date

• October 1996

publisher

• Society for Industrial & Applied Mathematics (SIAM)  Publisher

published in

• SIAM Journal on Matrix Analysis and Applications  Journal

keywords

• Approximate Minimum Degree Ordering Algorithm
• Graph Algorithms
• Ordering Algorithms
• Quotient Graph
• Sparse Matrices

Digital Object Identifier (DOI)

• 10.1137/S0895479894278952

start page

• 886

end page

• 905

volume

• 17

issue

• 4

URL

• http://dx.doi.org/10.1137/s0895479894278952