Diagonalization of very large (but very simple) sparse matrix

Question

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:

1. It is symmetric.

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

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

Answer 1

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

Answer 2

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)