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