Intel Extended Eigensolver (for sparse matrices) extremely slow

3
votes

I am trying to find the eigenvalues of rather large sparse matrices, and I have the Intel MKL libraries installed. I am writing in Fortran 90. Since my matrix is sparse, I was hoping to use the Extended Eigensolver routines to find the eigenvalues. However I find it is very slow compared to the dense MKL routines. I wrote a code to generate my matrices of various sizes 2**N x 2**N and found the eigenvalues variously using the following routines:

dsyev()
dsyevr()
dsyevd()
dsyev_f95()
dsyevr_f95()
dsyevd_f95()
dfeast_scsrev()

the last one is the Extended Eigensolver routine. I don't expect any difference between the f77 and f95 versions of the LAPACK routines, except that as far as I can tell, dsyevr_f95() does not have the JOBZ parameter, and therefore I cannot tell it to only compute eigenvalues (and not eigenvectors). As far as I can tell I also cannot tell the dfeast_scsrev() routine to only compute eigenvalues either.

I timed these routines for various matrix sizes, and I find that dfeast_scsrev() takes about 100 times longer than dsyevr_f95(), which already is a factor of 10 slower than the others because it is also computing the eigenvectors. This seems completely bizzare to me, and I am wondering if I am somehow doing something wrong. The results look like this:

time to build H is the time to construct the matrix

density of matrix is the fraction of non-zero elements

time to convert to sparse is the time to convert from dense to CSR format (negligible).

Times listed in the table are the times to call the subroutine which calls the relevant LAPACK/MKL routines. Times are in clock time, not wall time

 ###############################################################################

                                 N=            4
                    time to build H:           0
               dimensions of matrix:          16 x          16

         density of matrix:   0.140625000000000
 time to convert to sparse:            0
 time to run dfeast_scsrev:         1130
                                            dsyev       dsyevr      dsyevd
                           ----------------------------------------------------
                       f77 versions:         150          10          30
                       f95 versions:          30          30          20
                    sparse version :        1180

 ###############################################################################

                                 N=            5
                    time to build H:           0
               dimensions of matrix:          32 x          32

         density of matrix:   0.109375000000000
 time to convert to sparse:            0
 time to run dfeast_scsrev:           50
                                            dsyev       dsyevr      dsyevd
                           ----------------------------------------------------
                       f77 versions:          20          30          40
                       f95 versions:          40          30         130
                    sparse version :          90

 ###############################################################################

                                 N=            6
                    time to build H:           0
               dimensions of matrix:          64 x          64

         density of matrix:   6.250000000000000E-002
 time to convert to sparse:            0
 time to run dfeast_scsrev:          170
                                            dsyev       dsyevr      dsyevd
                           ----------------------------------------------------
                       f77 versions:          20          90         110
                       f95 versions:          30          60          90
                    sparse version :         340

 ###############################################################################

                                 N=            7
                    time to build H:           0
               dimensions of matrix:         128 x         128

         density of matrix:   3.515625000000000E-002
 time to convert to sparse:            0
 time to run dfeast_scsrev:          520
                                            dsyev       dsyevr      dsyevd
                           ----------------------------------------------------
                       f77 versions:         180         140         140
                       f95 versions:         190         270         140
                    sparse version :         740

 ###############################################################################

                                 N=            8
                    time to build H:          10
               dimensions of matrix:         256 x         256

         density of matrix:   1.739501953125000E-002
 time to convert to sparse:           10
 time to run dfeast_scsrev:         3750
                                            dsyev       dsyevr      dsyevd
                           ----------------------------------------------------
                       f77 versions:         350         270         520
                       f95 versions:         420         790         410
                    sparse version :        4240

 ###############################################################################

                                 N=            9
                    time to build H:           0
               dimensions of matrix:         512 x         512

         density of matrix:   1.074218750000000E-002
 time to convert to sparse:           10
 time to run dfeast_scsrev:        33250
                                            dsyev       dsyevr      dsyevd
                           ----------------------------------------------------
                       f77 versions:         570        1050         820
                       f95 versions:        1060        2880         500
                    sparse version :       33670

 ###############################################################################

                                 N=           10
                    time to build H:          10
               dimensions of matrix:        1024 x        1024

         density of matrix:   5.859375000000000E-003
 time to convert to sparse:           80
 time to run dfeast_scsrev:       222820
                                            dsyev       dsyevr      dsyevd
                           ----------------------------------------------------
                       f77 versions:        1870        2130        2230
                       f95 versions:        2290        8110        2010
                    sparse version :      223570

My code can be viewed here

I have confirmed that all routines produce the same eigenvalues.

So my questions is, is this correct? Why is the sparse eigensolver so slow? Is there something I'm doing wrong or that I can do to speed it up? Note everything here is run sequentially, no parallelization. And lastly, can anyone recommend an alternative sparse eigensolver? Given the sparseness of these matrices (and that I want to get up to N=16 or more) I would think that a sparse solver would be far more efficient than the dense LAPACK solvers.

1
matrixfortransparse-matrixlapackintel-mkl
I don't necessarily need all eigenpairs, however I am finding all eigenvalues using the LAPACK routines, so I'm surprised that they would be so much faster. I haven't tested looking for just a few eigenvalues. Is there a reason why a sparse solver would be slower for finding all eigenvalues? – Kai
If necessary, in addition to comp.sci forum, it may be very useful to post a question in the Intel forum (a bit later...) software.intel.com/en-us/forums/intel-math-kernel-library – roygvib
sir, it is two years later, do you find any alternative high performance sparse eigensolver? could you please give me some advice? – Xu Hui
@XuHui unfortunately I never did figure this issue out, I have not needed a sparse eigensolver since and have been able to just use regular eigensolvers – Kai

1 Answers

0
votes

I do not have experience with the library you are using, so I can't comment on its performance. If it is a requirement that the code is in Fortran, I have had excellent results on symmetric sparse matrices using JADAMILU, which performs automatic preconditioning and has fairly straightforward documentation (as compared to some old school stuff like ARPACK). If you can get away from using Fortran, I'd recommend PySparse.

EDIT: After looking at your test data, I'm not too surprised at your results. There is significant performance overhead in using a sparse solver, especially for the relatively small size of the arrays you're using. Where you typically get your benefit is in memory, since for large sparse arrays sparse storage methods compresses your data significantly.