matlab enclosure

[berkCEE]

Hi all,

I have a 2000X2000 matrix that I need to find its eigenvalues and eigenvectors. The matrix entries are real, double, it is unsymmetric, and the data is in matlab. I was told that there is a routine here that is much faster than matlab's, but it may not have matlab's interface yet. Could anyone help me find out about it?

(I was told that the routine is DGEEV, though I couldn't find any such routine using the search engine. DHSEIN or DTREVC sound the closest, I guess)

Many thanks.

[Julien Langou]

Hello,

Matlab's routine eig is basically calling LAPACK routine DGEEV when A is not symmetric. The LAPACK library provided with Matlab is currently the version 3.0. The thing is that LAPACK has just been updated (few weeks ago: see http://www.netlib.org/lapack/lapack-3.1.0.changes) and one of the main contribution is a new nonsymmetric eigensolver thanks to Ralph Byers and Karen Braman. The speed up that you can observe varies some (depends on the matrix property, the matrix size, the machine, etc.) but say that for the overall problem you get a factor of 3 as soon as the size of the matrix is greater than 500 (say).

So you are right at the present time LAPACK is way faster than Matlab (3 times). I bet this is a matter of months for MathWorks to update their LAPACK libraries. Then LAPACK and Mathworks will be even.

Julien.

[berkCEE]

Thanks Julien,

So that means that the new updates of LAPACK library are currently not available to matlab users, right?

Best,

[Julien Langou]

> So that means that the new updates of LAPACK library are currently not
> available to matlab users, right?

There is a classical trick that enables you to access LAPACK-3.1 right now from
Matlab. You can force Matlab to use LAPACK-3.1 instead of LAPACK-3.0 through a
LD_PRELOAD statement. Since LAPACK-3.1 is backward compatible with LAPACK-3.0,
this is safe. It's pretty clear that by doing this you'll go in wild land and
if something does not work, well, you can certainly not complain to MathWorks.
But it's easy to try and the gain can be huge. This is a temporary trick and
you can forget it as soon as MathWorks will release Matlab with LAPACK-3.1.

On the Pentium IV, I am working with

A- Download LAPACK-3.1 and install it.

B- Create a shared LAPACK-3.1 library:
cc -shared INSTALL/slamch.o INSTALL/second.o INSTALL/dlamch.o INSTALL/dsecnd.o INSTALL/ilaver.o INSTALL/lsame.o SRC/*o -lm -lg2c -o liblapack.so

C- Call matlab with the LD_PRELOAD flag:
LD_LIBRARY_PATH='/opt/matlab_2006a/bin/glnx86/' LD_PRELOAD='/home/faculty/langou/lapack-3.1.0/liblapack.so:/opt/matlab_2006a /bin/glnx86/libmkl.so' matlab -nojvm

D- Enjoy. Type eig(A) for example.

In the case of the nonsymmetric eigenvalue probem (NEP), you want to use
LAPACK-3.1 instead of LAPACK-3.0 for two reasons. First, LAPACK-3.1 has an
implementation of the new Braman-Byers-Mathias Hessenberg QR algorithm with the
small bulge multi-shift and aggressive early deflation [1,2]. Second,
LAPACK-3.1 also have a new implementation for the Hessenberg reduction routine
from Quintana-Orti and van-de-Geijn [3]. All in all this makes dgeev way faster
than previously.

[1] K. Braman, R. Byers and R. Mathias, The Multi-Shift QR Algorithm Part
I: Maintaining Well Focused Shifts, and Level 3 Performance, SIAM
Journal of Matrix Analysis, 23:929-947, 2002.
[2] K. Braman, R. Byers and R. Mathias, The Multi-Shift QR Algorithm Part
II: Aggressive Early Deflation, SIAM Journal of Matrix Analysis,
23:948-973, 2002.
[3] G. Quintana-Orti and R. van de Geijn, Improving the Performance of
Reduction to Hessenberg Form. ACM Transactions on Mathematical Software,
32(2):180-194, June 2006.

Here are some results for the Matlab command eig(A) where A is randn(n) matrix.

Code: Select all

===========================================================================
Experiments using Matlab on Pentium IV 3.00GHz, 512KB cache, running Linux
===========================================================================
 n      Matlab   hacked     speedup
 100    0.06     0.05       1.20
 150    0.17     0.12       1.41
 200    0.38     0.21       1.80
 250    0.78     0.36       2.16
 300    1.35     0.58       2.32
 350    2.15     0.85       2.52
 400    3.09     1.14       2.71
 450    4.65     1.51       3.07
 500    6.13     1.99       3.08
 550    8.45     2.70       3.12
 600   10.43     3.43       3.04
 650   13.25     4.09       3.23
 700   16.33     4.73       3.45
 750   20.40     5.55       3.67
 800   24.55     6.26       3.92
 850   29.57     7.27       4.06
 900   34.15     8.25       4.13
 950   40.56     9.40       4.31
1000   47.66    10.66       4.47
1050   55.20    12.11       4.55
1100   61.73    13.50       4.57
1150   71.57    15.03       4.76
1200   83.23    16.63       5.00
1250   93.10    18.32       5.08
1300  104.99    20.39       5.14
1350  116.85    22.50       5.19
1400  128.84    24.21       5.32
1450  146.04    26.95       5.41
1500  192.96    29.46       6.54
1550  ---.--    32.28       -.--
1600  ---.--    35.38       -.--
1650  ---.--    37.82       -.--
1700  ---.--    40.76       -.--
1750  ---.--    44.23       -.--
1800  ---.--    47.82       -.--
1850  ---.--    51.47       -.--
1900  ---.--    55.31       -.--
1950  ---.--    60.74       -.--
2000  ---.--    63.55       -.--
===========================================================================