A Block-LU Update for Large-Scale Linear Programming

From MaRDI portal
A Block-$LU$ Update for Large-Scale Linear Programming





The paper deals with the simplex method for the standard large sparse linear programming problem. Stable and efficient updates to the basis matrix factors are vital to the computational success. The updating technique of \textit{P. E. Gill}, \textit{W. Murray}, the second author and \textit{M. H. Wright} [SIAM J. Sci. Stat. Comput. 5, 562--589 (1984; Zbl 0559.65042)], based on the block-LU factors of an expanding basis is examined. The main conclusions are: a) the block-LU update technique is a viable alternative to the standard updating technique of Bartels and Golub [cf. \textit{R. H. Bartels}, Numer. Math. 16, 414--434 (1971; Zbl 0197.43305)] when vectorization is available, b) numerical experiments on a CRAY Y-MP show the block-LU update to be superior to Bartels-Golub updating on 27 of 30 large, sparse test problems, c) the block-LU update possesses the same stability properties as the update of Bartels and Golub.




Cited in
(23)








This page was built for publication: A Block-$LU$ Update for Large-Scale Linear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3988985)