A Minimal Storage Implementation of the Minimum Degree Algorithm
Alan D. George, Joseph W. H. Liu · SIAM Journal on Numerical Analysis · 1980
We describe an efficient implementation of the minimum degree algorithm, which experience has shown to be effective in finding low fill orderings for sparse positive definite systems. The algorithm is heuristic; at each step in the elimination, the variable chosen to eliminate next is one which minimizes the multiplications performed at that step. Thus, some representation of the partially factored matrix is required at each step of the ordering. Previous implementations have stored this representation in an explicit form with a data structure which allows the matrix structure to change as the ordering proceeds. The implementation we describe in this paper works only with the graph of the original matrix, and all data structures used are fixed throughout the execution of the algorithm. In contrast to most previous implementations, the total storage requirement of the algorithm is known before execution. Several effective techniques for speeding up the algorithm are described, and numerical experiments on some problems arising in finite element applications suggest that for these problems the execution time is $O(N)$, where N is the number of equations.