ACCELERATING LP ALGORITHMS

Abstract

Winograd has given a new method for computing inner products. Under certain circumstances, when a series of inner products must be calculated, using Winograd's scheme is more efficient than the standard (naive) method. Winograd points out that his method does matrix multiplication up to twice as fast as the usual scheme and notes similar acceleration for matrix inversion and the solution of linear equations. This report describes how Winograd's method can speed up linear programming algorithms, in particular the revised simplex method.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1968
Accession Number
AD0678502

Entities

People

  • B. L. Fox

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computers
  • Corporations
  • Equations
  • Heuristic Methods
  • Inversion
  • Iterations
  • Linear Programming
  • New Jersey
  • Simplex Method
  • Sparse Matrix
  • Standards

Fields of Study

  • Physics

Readers

  • Approximation Theory.
  • Marine Propulsion Engineering and Naval Architecture
  • Operations Research