How is reinversion performed in PFI (Product Form of Inverse) Revised Simplex.

[Sai Sriram]

Hello, 

While doing Revised Simplex using Product Form of Inverse, We have product of set of Eta Vectors(Elementary Matrix) to describe the Basis Inverse after certain number of steps in simplex. Considering Initial Basis to be [I] - identity matrix, we may just need to perform pre-multiplication or post-multiplication of set of Eta Vectors with the other vector/matrix during the iteration of simplex.

Hence, At this stage we only have set of Elementary Matrices, How do we reinvert them???

I did not find any proper explanation to this anywhere? Do we perform product of all Elementary matrices to get current Basis Inverse and then perform Gauss Jordan method over it to find the set of Elementary matrices once again. This means that we are going to need to store current Basis Inverse again. plus we perform several set of row transformations once more.

How is this actually done??? Can we re-invert using just the existing set of Elementary matrices..

Thank you in advance.

[Miles Lubin]

This is pretty much off topic, but a good reference on this is Achim Koberstein's thesis: http://digital.ub.uni-paderborn.de/hs/content/titleinfo/3885.

On page 24, section 3.1.5 he describes how to invert an elementary matrix. I doubt Gurobi uses this method though. The thesis also covers more efficient and modern methods like sparse LU factorization and updates.