A Block-$LU$ Update for Large-Scale Linear Programming

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, we examine a method based on the block-$LU$ factors of an expanding basis. The partitioned matrix involved was introduced by Bisschop and Meeraus [Math. Programming, 13 (1977), pp. 241–254], [Math. Programming, 18 (1980), pp. 7–15]. The update itself was proposed by Gill, Murray, Saunders, and Wright [SIAM J. Sci. Statist. Comput., 5 (1984), pp. 562–589].The main advantages of the block-$LU$ update are that it is stable, it vectorizes well, and compared to the product-form update, the nonzeros increase at about two-thi...