# 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:

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.

• I use the MKL library implementation of the FEAST algorithm. Dec 16, 2019 at 16:13
• Thanks, I'll look it up Dec 16, 2019 at 16:17

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