Accession Number : ADA398632
Title : The Computational Complexity of the Minimum Degree Algorithm
Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
Personal Author(s) : Heggernes, P. ; Eisestat, S. C. ; Kumfert, G. ; Pothen, A.
PDF Url : ADA398632
Report Date : DEC 2001
Pagination or Media Count : 13
Abstract : 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.
Descriptors : *ALGORITHMS, *COMPUTATIONS, *SPARSE MATRIX, GRAPHS, VARIATIONS, STORAGE, LINEAR ALGEBRAIC EQUATIONS.
Subject Categories : Numerical Mathematics
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE