The Computational Complexity of the Minimum Degree Algorithm

[摘要] 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.

[发布日期] 2001-12-01 [发布机构] Lawrence Livermore National Laboratory

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