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.
|PDF (with pauses)||IMA-NLAO_07a.pdf|
|PDF (without pauses)||IMA-NLAO_07a_NoPause.pdf|