Browse Prior Art Database

Using Fast Matrix Multiplication to Find Basic Solutions

IP.com Disclosure Number: IPCOM000116742D
Original Publication Date: 1995-Oct-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 47K

Publishing Venue

IBM

Related People

Beling, P: AUTHOR [+2]

Abstract

This invention improves the computation time to find a basic solution to a system of linear constraints in standard form when a non-basic solution is given. More specifically, given any nonnegative solution to a given system of linear equations, the problem is to find a solution that uses only a set of linearly independent columns of the system. This problem is fundamental in linear programming and arises in the practice of interior point methods. The best previously known algorithms perform as many operations as the squared number of equations times the number of variables in the system.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 67% of the total text.

Using Fast Matrix Multiplication to Find Basic Solutions

      This invention improves the computation time to find a basic
solution to a system of linear constraints in standard form when a
non-basic solution is given.  More specifically, given any
nonnegative solution to a given system of linear equations, the
problem is to find a solution that uses only a set of linearly
independent columns of the system.  This problem is fundamental in
linear programming and arises in the practice of interior point
methods.  The best previously known algorithms perform as many
operations as the squared number of equations times the number of
variables in the system.

      The invention is based on reducing much of the computation
involved to matrix multiplication.  Consequently, the complexity
bounds in their most general form are a function of the complexity of
matrix multiplication.

      The invented algorithm works iteratively.  During each
iteration, it works with a given basis and a small number of
additional non-basic columns.  These non-basic columns (and no
others) are first brought into canonical form with respect to the
basis.  The resulting subproblem is then solved and a new basic
sequence is identified.  The main computational work in the algorithm
is divided between that used to bring each new set of columns into
canonical form and that used to maintain the canonical form as each
of these columns is either added to the basis or dropped from further
c...