Saturday, July 19, 2008

Invert.exe performance

This model shows that my external solver INVERT.EXE is much faster than Cplex in inverting dense matrices. Obviously this is a case where INVERT is at its best, and Cplex is at a disadvantage, so this is not a poor performance of Cplex. These models are just not suited for a sparse LP solver.

Here is the model:

$ontext

Invert the Pei test matrix

Erwin Kalvelagen, july 2008

Command line arguments:
--n=integer order of the matrix
--alpha=real scalar defining the Pei matrix
--method=1 invert using equations A AINV = I
--method=2 invert using equations A AINV = I using advanced basis
--method=3 invert using external solver


Reference:

Erwin Kalvelagen
SOLVING SYSTEMS OF LINEAR EQUATIONS WITH GAMS
http://www.amsterdamoptimization.com/pdf/lineq.pdf

ML Pei,
A test matrix for inversion procedures,
Communications of the ACM,
Volume 5, 1962, page 508.

$offtext

*
* defaults
*
$if not set n $set n 100
$if not set method $set method 1
$if not set alpha $set alpha 1

scalar alpha /%alpha%/;

set i /i1*i%n%/;
alias (i,j,k);

parameter a(i,j);
a(i,j)=1;
a(i,i)=1+alpha;

parameter ident(i,j);
ident(i,i)=1;

variables
ainv(i,j)
dummy
;

equations
e(i,j)
edummy
;

edummy.. dummy =e= 0;
e(i,j).. sum(k, a(i,k)*ainv(k,j)) =e= ident(i,j);

model m /all/;

option iterlim=1000000;



$if "%method%"==1 solve m minimizing dummy using lp;

$ifthen "%method%"==2

edummy.m=1;
e.m(i,j)=1;
dummy.m=0;
ainv.m(i,j)=0;
solve m minimizing dummy using lp;

$endif

$ifthen "%method%"==3

execute_unload 'a.gdx',i,a;
execute '=invert.exe a.gdx i a b.gdx pinva';
parameter pinva(i,j);
execute_load 'b.gdx',pinva;

$endif


We have implemented three methods of calculating the inverse.

  1. Method=1 uses the LP solver to solve A * invA = I.
  2. Method=2 is as method=1 but we use an advanced basis to speed up the solver.
  3. Method=3 is calling the external solver INVERT.EXE

For more information see: http://www.amsterdamoptimization.com/pdf/lineq.pdf.

Some timings are listed below (all times in seconds):



             method=1   method=2   method=3
n=50 0.637 0.433 0.027
n=100 8.267 4.036 0.055
n=200 313.236 53.395 0.118


The timings are taken from the last line in the log file. E.g.:

--- Job Untitled_36.gms Start 07/19/08 15:46:36
GAMS Rev 227 Copyright (C) 1987-2008 GAMS Development. All rights reserved
Licensee: Erwin Kalvelagen G070509/0001CE-WIN
GAMS Development Corporation DC4572
--- Starting compilation
--- Untitled_36.gms(81) 3 Mb
--- Starting execution: elapsed 0:00:00.004
--- Untitled_36.gms(69) 5 Mb
----------------------------------------
INVERT: matrix inversion
Erwin Kalvelagen, Amsterdam Optimization
----------------------------------------
DLL:GDX Library May 1, 2008 22.7.2 WIN 4701.4799 VIS x86/MS Windows
GDXin:a.gdx
Input set:i
Input parameter:a
LAPACK DGESV, n= 200
GDXout:b.gdx
Output parameter:pinva
Done
--- Untitled_36.gms(71) 5 Mb
--- GDXin=C:\projects\test\b.gdx
--- Untitled_36.gms(71) 6 Mb
*** Status: Normal completion
--- Job Untitled_36.gms Stop 07/19/08 15:46:36 elapsed 0:00:00.118