A Matrix Factorization and Its Application to Large-Scale Linear Programming

Abstract

As an alternative to the LU matrix factorization, we consider a factorization that uses the lower triangular part of the original matrix as one factor and computes the other factors as a product of rank-one update matrices. After reviewing and improving the time complexity, the requirements, the stability and the efficiency of this method, we derive a stable factorization algorithm which we implement in FORTRAN77 within the framework of the simplex algorithm for linear programming. A comparison of our numerical results with those obtained through the code MINOS 5.3 indicate that our method may be more efficient than an ordinary LU decomposition for some matrices whose order ranges between 28 and 1481, especially when these matrices are almost triangular.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1989
Accession Number
ADA211293

Entities

People

  • Pierre F. Demazancourt

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Composite Materials
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computers
  • Decomposition
  • Frequency
  • Linear Programming
  • Numbers
  • Operations Research
  • Optimization
  • Permutations
  • Sequences
  • Simplex Method
  • United States

Fields of Study

  • Computer science

Readers

  • Linear Algebra
  • Operations Research