Abstract. An Approximate Minimum Degree ordering algorithm (AMD) 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 on 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. AMD is often faster and produces better orderings than general nested dissection for a wide range of matrices. Keywords: approximate minimum degree ordering algorithm, quotient graph, sparse matrices, graph algorithms, ordering algorithms AMS classi cations: 65F50, 65F05. 1. Introduction. A common technique for solving large sparse symmetric linear systems of the form Ax = b is to precede the numerical factorization by a symmetric reordering chosen so that pivoting down the diagonal in order on the resulting permuted matrix PAP T = LL T produces much less ll-in and work than computing the factors of A by pivoting down the diagonal in order. This reordering is computed using only information on the matrix structure without taking account of numerical values. If the matrix A is positive-de nite 19], a Cholesky factorization can be used. This technique of preceding the numerical factorization with a symbolic analysis can also be extended to non-symmetric systems although the numerical factorization phase must allow for subsequent numerical pivoting 1, 2, 13]. The goal of the preordering is to nd a permutation matrix P that results in the least amount of ll-in. Unfortunately, this problem is NP-complete 30], so heuristics are used. The minimum degree ordering algorithm is one of the most widely used heuristics, since it produces factors with relatively low ll-in on a wide range of matrices. Because of this, the algorithm has received much attention over the past three decades. The algorithm is a symmetric analogue of Markowitz' method 24] and was rst proposed by Tinney and Walker 29] as algorithm S2. Rose 25, 26] developed a graph theoretical model of Tinney and Walker's algorithm and renamed it the minimum degree algorithm, since it performs its pivot selection by selecting from a graph a node of minimum degree. Later implementations have dramatically improved the time and memory requirements of Tinney and Walker's method, while maintaining the basic idea of selecting a node or set of nodes of minimum degree. These have reduced the memory complexity so that the algorithm can operate within the storage of the original matrix, and have reduced the amount of work needed to keep track of the We would like to recognize the role of the Workshop \Sparse Days at Saint-Girons" in providing the stimulation and location for many discussions on this paper y ENSEEIHT,
Minimum degree orderings, such as approximate minimum degree ordering (AMD) are used to reduce fill-in REF .
An Approximate Minimum Degree Ordering Algorithm
SIAM Journal on Matrix Analysis and Applications
Computer Science Mathematics