## 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

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:36GAMS Rev 227  Copyright (C) 1987-2008 GAMS Development. All rights reservedLicensee: 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``