When we want to solve a large, sparse system of linear equations
using an LP solver we expect this to be reasonably fast. After all, solving systems of equations is what an LP solver does all the time. So we introduce a zero objective and solve. With Gurobi a sample problem gives:
Iteration Objective Primal Inf. Dual Inf. Time
Solved in 5199 iterations and 25.19 seconds
Actually we can much improve on this. By specifying an advanced basis. We know the equations (slacks) will be non-basic in the solution and all the variables will be basic. If we set up an advanced basis for this we see for the same problem:
Solved in 0 iterations and 0.45 seconds
Indeed no simplex iterations were needed: just an invert.
In response to a comment about Octave: that is still faster:
- Not completely fair of course: the LP solver does still a lot of extra things (scaling, pricing etc.).
- Note that I used a sparse matrix in Octave. Not sure what method they use to solve this system.
- This was a structured test matrix: see: http://www.public.iastate.edu/~akmitra/aero361/design_web/Laplace.pdf. For more unstructured matrices Gurobi may do much better relative to Octave.