I have a $10^5 \times 10^5$ matrix and I need its smallest eigenvalue (not the the smallest in absolute value, but actually the lowest) and the associated eigenvector (I know the eigenvalue to be non-degenerate). The matrix is huge, but it has several nice properties:
It is symmetric.
The density is extremely low: the proportion of non-zero entries is much less than $0.1\%$. In each row there are only (maximum) $15$ non-zero entries.
There are only $10$ different values among the entries.
I'd like to find a very efficient way to compute the eigenvalue and the eigenvector. Standard diagonalization techniques are too costful, and even Lanczos algorithm is not entirely useful in this case.