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. We present a simple but novel combinatorial algorithm for computing an exact minimum degree elimination ordering in $O(nm)$ time. Our approach uses a careful amortized analysis, which also allows us to derive output-sensitive bounds for the running time of $O(\min\{m\sqrt{m^+}, \Delta m^+\} \log n)$, where $m^+$ is the number of unique fill edges and original edges encountered by the algorithm and $\Delta$ is the maximum degree of the input graph. Furthermore, we show there cannot exist a minimum degree algorithm that runs in $O(nm^{1-\varepsilon})$ time, for any $\varepsilon > 0$, assuming the strong exponential time hypothesis. Our fine-grained reduction uses a new sparse, low-degree graph construction called \emph{$U$-fillers}, which act as pathological inputs and cause any minimum degree algorithm to exhibit nearly worst-case performance.

• Algorithms and Theory