Diagonalization of very large (but very simple) sparse matrix 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.
 A: As $A$ is symmetric, we have $\max|\lambda_i|=\|A\|_2$ and $\|A\|_1 = \|A\|_{\infty}.$ Furthermore $\|A\|_2 \leq \sqrt{\|A\|_1\|A\|_{\infty}}$, see here. If we put all this together, we get an easy-to-calculate upper bound for the largest eigenvalue $\lambda_{\max}$:
$$
\lambda_{\max} \leq \max|\lambda_i|=\|A\|_2 \leq\sqrt{\|A\|_1\|A\|_{\infty}}
=\sqrt{\|A\|_{\infty}\|A\|_{\infty}} = \|A\|_{\infty}
$$
Let $c = \|A\|_{\infty}.$ As all eigenvalues of $A$ are smaller than $c,$ all eigenvalues of $cI-A$ are non-negative, and the smallest eigenvalue of $A$ is the largest eigenvalue of $cI-A.$ As the eigenvalue is non-degenerate, you can use ordinary power iteration to get the largest eigenvalue $\lambda_c$ and the associated eigenvector $v$ of $cI-A.$ The eigenvalue $\lambda$ you are looking for is $\lambda = c-\lambda_c$, the eigenvector is $v.$
A: You can use Gershgorin Circle Theorem to get a lower bound $\lambda_{GCT}$ for $\lambda_{min}$ and then use that as a starting point for inverse iteration (https://en.wikipedia.org/wiki/Inverse_iteration).
(I would have just added this as a comment on Reinhard Meier's answer but don't have the rep)
