On the use of dense matrix techniques within sparse simplex

In this paper the authors discuss some instances where dense matrix techniques can be utilized within a sparse simplex linear programming solver. The main emphasis is on the use of the Schur complement matrix as a part of the basis matrix representation. This approach enables to represent the basis matrix as an easily invertible sparse matrix and one or more dense Schur complement matrices. The authors describe the present variant of this method which uses updating of the QR factorization of the Schur complement matrix. They also discuss some implementation issues of the LP software package which is based on this approach.