The Computational Complexity of the Minimum Degree Algorithm | Zendy

Pinar Heggernes | Zendy; Stanley C. Eisenstat | Zendy; G Kumfert | Zendy; Alex Pothen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Computational Complexity of the Minimum Degree Algorithm

Author(s) -

Pinar Heggernes,

Stanley C. Eisenstat,

G Kumfert,

Alex Pothen

Publication year - 2001

Publication title -

osti oai (u.s. department of energy office of scientific and technical information)

Language(s) - English

Resource type - Reports

DOI - 10.2172/15002765

Subject(s) - degree (music) , implementation , computational complexity theory , algorithm , computer science , computation , matrix (chemical analysis) , sparse matrix , mathematics , physics , materials science , quantum mechanics , acoustics , composite material , gaussian , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research