A Spike Collective Dynamic Factorization Algorithm for the Simplex Method
A dynamic factorization algorithm is developed which uses a partition of the basis to permit the simplex method to be executed from a small working inverse and a small, sparse triangular submatrix of the basis. This partition is maintained dynamically using spike swapping in a way which seeks to keep the size of the working inverse as small as possible. The algorithm is intended for use in solving general large scale linear programming problems. It is especially well suited for problems whose simplex basis has a small number of spikes after application of the Hellerman and Rarick P<sup>3</sup> procedure. Preliminary computation experience and direct comparison with Reid's sparsity-exploiting variant of the Bartels-Golub decomposition for LP bases indicate that a significant reduction is obtained with the dynamic factorization approach in the nonzero elements needed to represent the basis inverse. For all bases considered the number of nonzero elements needed to represent the inverse immediately prior to rein version is reduced by a factor of 1.7 to 20.
