Parallel basis matrix triangularisation for hyper-sparse LP problems

Invited talk at the joint EUROPT-OMS Meeting 2007: 4th July 2007

J. A. J. Hall

Abstract

For linear programming (LP) problems where the revised simplex method out-performs interior point methods, the pivotal column, shadow prices and pivotal row are generally sparse. This property of LP problems is referred to as hyper-sparsity. It will be shown that the basis matrices of hyper-sparse LP problems are generally highly reducible, and that the dominant cost of matrix inversion is that of identifying the irreducible component via a triangularisation procedure. This talk will describe such a procedure, discuss its parallelisation and give results for both a serial simulation and a prototype parallel implementation.