A Block-LU Update for Large-Scale Linear Programming
Abstract
Stable and efficient updates to the basis matrix factors are vital to the simplex method. The best updating method depends on the machine in use and how the update is implemented. For example, the classical product-form update can take advantage of the vector hardware on current supercomputers, and this helps compensate for its well known drawbacks. Conversely, the method of Bartels and Golub performs well on conventional machines, but is difficult to vectorize. With vectorization in mind, a method is examined based on the block-LU factors of an expanding basis. The partitioned matrix involved was introducted by Bisschop and Meeraus (1977, 1980). The update itself was proposed by Gill, Murray, Saunders and Wright (1984). The main advantages of the bloc-LU update are that it is stable, it vectorizes well, and compared to the product-form update, the nonzeros increase at about two thirds the rate. The update has been incorporated into MINOS and tested on 30 large, sparse linear programming problems. Results are given from runs on the Cray Y-MP.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1990
- Accession Number
- ADA219849
Entities
People
- Michael Saunders
- Samuel K. Eldersveld
Organizations
- Stanford University