The Computational Complexity of the Minimum Degree Algorithm

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2001
Accession Number
ADA398632

Entities

People

  • A. Pothen
  • G. Kumfert
  • P. Heggernes
  • S. C. Eisestat

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computational Complexity
  • Computer Science
  • Computers
  • Contracts
  • Elimination
  • Graph Theory
  • Sparse Matrix
  • Universities
  • Virginia

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Linear Algebra
  • Systems Analysis and Design