A Fast Algorithm That Makes Matrices Optimally Sparse.

Abstract

Under a non-degeneracy assumption on the non-zero entries of a given sparse matrix, a polynomially-bounded algorithm is presented that performs row operations on the given matrix which reduce it to a sparsest possible matrix with the same row space. For each row of the matrix, the algorithm performs a maximum cardinality matching on the bipartite graph associated with a submatrix which is induced by that row. The dual of the optimal matching then species the row operations that will be performed on that row. Also described is a variant algorithm that processes the matrix in place, thus conserving storage and time. The modifications needed to apply the algorithm to matrices that do not necessarily satisfy the non-degeneracy assumption are also described. A particularly promising application of this algorithm is in the reduction of linear constraint matrices. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1982
Accession Number
ADA120902

Entities

People

  • Alan J. Hoffman
  • S. Thomas Mccormick

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Cancellation
  • Contracts
  • Coverings
  • Equations
  • Graph Theory
  • Inequalities
  • Linear Programming
  • Linear Systems
  • Military Research
  • New York
  • Operations Research
  • Optimization
  • Sparse Matrix
  • Standards
  • State Governments
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.
  • Linear Algebra

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers