The Computational Complexity of the Minimum Degree Algorithm

Heggernes, P ; Eisenstat, S C ; Kumfert, G ; Pothen, A

Lawrence Livermore National Laboratory

关键词: Lawrence Livermore National Laboratory;    Storage;    Algorithms;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;   

DOI  :  10.2172/15002765
RP-ID  :  UCRL-ID-148375
RP-ID  :  W-7405-ENG-48
RP-ID  :  15002765

美国|英语

来源: UNT Digital Library

【 摘 要 】

The Minimum Degree algorithm, one of the classical algorithms of sparse matrix computations, is widely used to order graphs to reduce the work and storage needed to solve sparse systems of linear equations. There has been extensive research involving practical implementations of this algorithm over the past two decades. However, little has been done to establish theoretical bounds on the computational complexity of these implementations. We study the Minimum Degree algorithm, and prove time complexity bounds for its widely used variants.