Report Number: CS-TR-72-301
Institution: Stanford University, Department of Computer Science
Title: Product form of the Cholesky factorization for large-scale linear programming.
Author: Saunders, Michael A.
Date: August 1972
Abstract: A variation of Gill and Murray's version of the revised simplex algorithm is proposed, using the Cholesky factorization ${BB}^T = {LDL}^T$ where B is the usual basis, D is diagonal and L is unit lower triangular. It is shown that during change of basis L may be updated in product form. As with standard methods using the product form of inverse, this allows use of sequential storage devices for accumulating updates to L. In addition the favorable numerical properties of Gill and Murray's algorithm are retained. Cloase attention is given to efficient out-of-core implementation. In the case of large-scale block-angular problems, the updates to L will remain very sparse for all iterations.