### Julian Hall (University of Edinburgh)

#### Parallel matrix inversion for the revised simplex method: a study

*ERGO Optimization day: Tuesday 13 June 2006 at 14.00, JCMB 5327*

##### Abstract

The revised simplex method for solving linear programming LP problems
requires the solution of Bã_{q} = a_{q} and
Bπ = e_{p}, where B is the basis matrix, a_{q} is column q
of the (sparse) constraint matrix and e_{p} is column p of the
identity matrix. Although the invertible representation of B is usually
obtained by an updating procedure, periodically it is necessary to form it
from scratch. As a crucial step towards the goal of a practical parallel
implementation of the revised simplex method, this talk considers the scope
for exploiting parallelism during basis matrix inversion.

For LP problems where the revised simplex method out-performs barrier
methods, the solutions of Bã_{q} = a_{q} and
Bπ = e_{p} 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 the
triangularisation procedure and discuss the scope for parallelising it.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*