A Fast Minimum Degree Algorithm and Matching Lower Bound

The minimum degree algorithm is one of the most widely-used heuristics for reducing the cost of solving large sparse systems of linear equations. It has been studied for nearly half a century and has a rich history of bridging techniques from data structures, graph algorithms, and scientific computing. In this paper, we present a simple but novel combinatorial algorithm for computing an exact minimum degree elimination ordering in O(nm) time, which improves on the best known time complexity of O(n3) and offers practical improvements for sparse systems with small values of m. Our approach leverages a careful amortized analysis, which also allows us to derive output-sensitive bounds for the running time of , where m+ is the number of unique fill edges and original edges that the algorithm encounters and Δ is the maximum degree of the input graph. Furthermore, we show there cannot exist an exact minimum degree algorithm that runs in O(nm1 – ∊) time, for any ∊ > 0, assuming the strong exponential time hypothesis. This fine-grained reduction goes through the orthogonal vectors problem and uses a new low-degree graph construction called U-fillers, which act as pathological inputs and cause any minimum degree algorithm to exhibit nearly worst-case performance. With these two results, we nearly characterize the time complexity of computing an exact minimum degree ordering.