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

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.)

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?
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?