#
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.

**Slides:**