Search
Join ACM

Richard H. Bartels

Research and Advances May 1 1969

The simplex method of linear programming using LU decomposition

Standard computer implementations of Dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. These implementations have bad round-off error properties. This paper gives the theoretical background for an implementation which is based upon the LU decomposition, computed with row interchanges, of the basic matrix. The implementation is slow, but has good round-off error behavior. The implementation appears as CACM Algorithm 350.
Systems and Networking

Advertisement

Author Archives

Research and Advances Jun 1 1968

Numerical Analysis: Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations

An implementation of Stiefel's exchange algorithm for determining a Chebyshev solution to an overdetermined system of linear equations is presented, that uses Gaussian LU decomposition with row interchanges. The implementation is computationally more stable than those usually given in the literature. A generalization of Stiefel's algorithm is developed which permits the occasional exchange of two equations simultaneously.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved