Using Deficiency Measure For Tiebreaking the Minimum Degree Algorithm

The minimum degree algorithm is known as an effective scheme for identifying a fill reduced ordering for symmetric, positive definite, sparse linear systems. Although the original algorithm has been enhanced to improve the efficiency of its implementation, ties between minimum degree elimination candidates are still arbitrarily broken. For many systems, the fill levels of orderings produced by the minimum degree algorithm are very sensitive to the precise manner in which these ties are resolved. This paper introduces several tiebreaking schemes for the minimum degree algorithm. Emphasis is placed upon a tiebreaking strategy based on the deficiency of minimum degree elimination candidates, which can consistently identify low fill orderings for a wide spectrum of test problems. The tiebreaking strategies are integrated into a quotient graph form of the minimum degree algorithm with uneliminated supernodes. Implementations of the enhanced forms of the algorithm are tested on a wide variety of sparse systems to investigate the potential of the tiebreaking strategies.