# Computation time of eigenvalues with ARPACK depends on what?

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?

• 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. Sep 7 '17 at 10:45
• 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. Apr 12 '20 at 14:04