The Evolution of the Minimum Degree Ordering Algorithm

TLDR

The minimum degree algorithm has been extensively studied over the past fifteen years, leading to many important enhancements. The paper aims to describe the historical development of these enhancements and to demonstrate their effectiveness in reducing execution time, while highlighting the need for an effective tie‑breaking strategy. The authors review the enhancements and conduct experiments to evaluate their impact on execution time. The study finds that the ordering quality is highly sensitive to the initial ordering, with changes causing up to a three‑fold variation in factorization cost, due to the absence of an effective tie‑breaking strategy.

Abstract

Over the past fifteen years, the implementation of the minimum degree algorithm has received much study, and many important enhancements have been made to it. This paper describes these various enhancements, their historical development, and some experiments showing how very effective they are in improving the execution time of the algorithm. A shortcoming is also presented that exists in all of the widely used implementations of the algorithm, namely, that the quality of the ordering provided by the implementations is surprisingly sensitive to the initial ordering. For example, changing the input ordering can lead to an increase (or decrease) of as much as a factor of three in the cost of the subsequent numerical factorization. This sensitivity is caused by the lack of an effective tie-breaking strategy, and the authors’ experiments illustrate the importance of developing such a strategy