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?