3
$\begingroup$

I am finding the eigenvalues of dense NxN Hermitian matrix which is calculated from a density operator in quantum physics. All the eigenvalues are needed as I need to calculate the sum of the absolute value of them. I would like to know whether there are good solvers for this problem that can run in parallel?

The problem size I am interested should be at least N=40000. The one I am currently using is the gsl library, which has the advantage that it takes no extra working memory except the matrix itself. However, the running time is close to 5 hours for N=20000 because of no parallelization. I am going to run the problem in computing cluster that has walltime limit of 3 days so my program is likely to be killed.

I have tried SLEPc, but it does not scale well for the dense matrix. The computation time with 8 cores is almost the same as single core gsl! Not to mention it takes more memory and less accurate result in my case.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

SLEPc is a library designed for the solution of large sparse eigenvalue problems, while your matrix is dense. The algorithms used by SLEPc are based on matrix-vector multiplication, and the performance of these algorithms is primarily limited by the available memory bandwidth rather than the number of processor cores.

You might be better off using a software library designed to solve dense eigenvalue problems. For example, if you use LAPACK's QR factorization algorithms, it will use BLAS library routines, some of which can make effective use of your eight cores.

However, the parallelization of dense eigenvalue problems is still an area of active research. See for example these recent conference talks:

http://web.eecs.utk.edu/~luszczek/conf/siamcse2013_eigvalsolv/

Improve this answer
$\endgroup$
2
  • $\begingroup$ That is why I am asking this question. I am quite disappointed after trying few. Do you think that the LAPACK one is really faster? I don't really need to calculate any eigenvectors $\endgroup$
    – unsym
    Jul 22, 2014 at 16:51
  • 1
    $\begingroup$ I think that LAPACK together with well optimized BLAS routines may well be faster than using SLEPc. Using MATLAB (which calls LAPACK and BLAS), I just computed the eigenvalues of a random symmetric 100000 by 10000 matrix in under 2 minutes (653 seconds of CPU time) on a Core i7 machine with 8 processors. This parallelized well. I'd expect that a matrix of size $N=400000$ could be handled in less than 2 hours. It takes $O(N^3)$ time, and the matrix would be 4 times larger, so time should grow by about $4^3=64$. $\endgroup$
    – Brian Borchers
    Jul 22, 2014 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.