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