Partial diagonalisation of large symmetric positive-definite band-diagonal matrices

Question

I want to partially diagonalise real sparse symmetric positive-definite matrices, that are of dimension $n = 10^5$ and I need on the order of $k = 500$ of the smallest eigenvalues and eigenvectors. The number of non-zero elements scales with $n$, and optionally I can arrange the matrices to be band-diagonal with the number of bands $\sim200$, independent of $n$.

Currently, I am using ARPACK (making no use of the banded structure), but the run-time is becoming prohibitive. I'm wondering whether the FEAST algorithm might be a good alternative, since having a good idea of what the spectrum will look like, I can confidently supply it with $[\lambda_{\min}, \lambda_{\max}]$. I have looked into other algorithms but am a bit overwhelmed by the number of choices.

My question is twofold.

1. Could the banded structure make a significant difference?
2. Are there specific algorithms that will outperform ARPACK? (Since as far as I know, it only makes use of the fact that $A$ is real and symmetric, not the other properties. Furthermore, I am not sure that $k = 500$ constitutes "a few eigenvalues" anymore, hence I am wondering whether other algorithms can outperform it.)

Answer 1

Generally, taking advantage of $A$'s structure (sparsity/bandedness) has no bearing on convergence rates but it will always improve the time to apply a matvec via the "reverse communication API" of ARPACK. Actually, it is not very clear what you might be doing, as $10^5$ is too big to store as an explicit dense matrix, you must be exploiting some kind of structure just to store/apply it, right?

Since you are looking at the smallest eigenpairs, I'd also consider inverse iteration to accelerate convergence to that end of the spectrum (using some flavor of Cholesky decomposition, either banded or sparse, to apply the inverse).

A matrix $10^5$ is not especially large for, say, a 2-D or 3-D FE/FD problem. Computing the Cholesky decomposition of such an A is a matter of routine. Bandedness is a more sensitive matter, as the bandwidth can have strong (superlinear) effect on the time/memory. A $10^5$ tridiagonal matrix is trivial to solve, but a $10^5$ banded matrix with bandwidth on the order $\sqrt N$ is a different animal. Where did your $A$ come from?