Skip to content

Opening book details…

Can I read A Fast Minimum Degree Algorithm and Matching Lower Bound on EtoBox?

A Fast Minimum Degree Algorithm and Matching Lower Bound by Robert Cummings; Matthew Fahrbach; Animesh Fatehpuria is a book available to read on EtoBox.

What is A Fast Minimum Degree Algorithm and Matching Lower Bound about?

The minimum degree algorithm is one of the most widelyused 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(n 3 ) 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 O(min(m √ m + , ∆m + ) log n), 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(nm 1-ε ) time, for any ε > 0, assuming the strong exponential time hypothesis. This fine-grained reduction goes through the orthogonal vectors problem and uses a new lowdegree graph construction called U -fillers, which act

Author
Robert Cummings; Matthew Fahrbach; Animesh Fatehpuria
Published
2021
Language
EN

More by Robert Cummings; Matthew Fahrbach; Animesh Fatehpuria

Browse all works by Robert Cummings; Matthew Fahrbach; Animesh Fatehpuria

Similar books