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
- Algorithm and Design Complexity — Anli Sherine; Mary Jasmine; Geno Peter; S. Albert Alexander (2023)
- A Breezing Proof of the KMW Bound — Corinna Coupette; Christoph Lenzen (2021)
- Wavelets and Fast Numerical Algorithms — Y. Meyer (1997)
- Energy-Efficient and Fast Data Collection in WSN Using Genetic Algorithm — Rahul Shingare; Satish Agnihotri (2023)
- A Novel Physarum-Based Optimization Algorithm for Shortest Path — Dan Wang; Zili Zhang (2021)
- Aquila Algorithm: A Systematic Review of Variants and Applications — Shivani Thapar; Amit Chhabra (2023)