2
$\begingroup$

My goal is to compute the k smallest eigenvalues of large symmetric sparse matrices. For this purpose I use python scipy's eigsh method in shift-invert mode which uses ARPACK. The matrices usually have around 900,000-1,000,000 rows. Now the computation time for these matrices on my system is normally around 30 minutes. The larger the matrices, the longer it takes - makes sense to me. Then there's one matrix that has only around 780,000 rows for which the computation time explodes. It takes around 10 hours for it to finish. Nothing else of importance running on the machine that would occupy noteworthy resources. I ran it three times, it always takes this long, and I doublechecked that I computed the matrix correctly. The only thing I noticed is that this matrix is even more sparse than the others.

So my question is, what could be happening here? What else can influence the computation time in this way except for the size of the matrix? Unfortunately I'm not that into linear algebra that I really understand what exactly ARPACK does (meaning, how Lanczos algorithm works). Any experts here?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ In shift-invert mode, ARPACK has to perform one or more factorizations of the matrix. For large matrices like you describe, this operation usually dominates the overall cost of the eigensolution. You would expect that a smaller and sparser matrix would take less computation time to factor but this is not always the case. You can test this by simply performing a LDL factorization of your matrix. $\endgroup$
    – Bill Greene
    Commented Sep 7, 2017 at 10:45
  • $\begingroup$ If your A is non-negative definite, find $\lambda_{max}$, then the largest eigenvalues of $\lambda_{max} I - A$ with normal arpack LM mode. An example is here on SO. $\endgroup$
    – denis
    Commented Apr 12, 2020 at 14:04

1 Answer 1

Reset to default
4
$\begingroup$

The eigen-distribution is governing the convergence of the Lanczos algorithm. When the eigenvalues are "well-separated", the Lanczos algorithm should be fairly fast. When some eigenvalues are clustered or multiples, computing the clustered (or multiple) eigenvalues slows down the convergence. The spread of the eigenvalues also matters (i.e. the ratio between the smallest to the largest). For further details, you can look at the ARPACK user's guide (and/or eigenvalue estimates in Parlett, "The symmetric eigenvalue problem").

  • If you ask for k-10, k-5, k-2, k, k+2, k+5, k+10 eigenvalues, does the time change dramatically? If so, it indicates the presence of "clustered/multiple" eigenvalues.
  • You could increase the size of the Krylov subspace (i.e. the parameter ncv).
  • The default tolerance on eigsh is machine precision. You could increase the tolerance.
Improve this answer
$\endgroup$
1
  • $\begingroup$ You can always ask the originator of ARPACK at [email protected] - he was the advisor of one of my coworkers PhD and is quite friendly. $\endgroup$
    – Matt
    Commented Sep 8, 2017 at 1:51

Your Answer

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

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