Compute the the dominant eigenvalue and its corresponding eigenvector of a sparse transition matrix

Question

I have a sparse $N\times N$ transition matrix (asymmetric), in which most entries are zero. I can use scipy.linalg.eig to compute all eigenvalues and eigenvectors and then find the dominant eigenvalue and its corresponding eigenvector. However, if $N$ is very large, it suffers from high computational expensive.

Is there some method more space-effective for the computation of the dominant eigenvalue and its eigenvector for a sparse transition matrix?

Answer 1

Yes---use the power iteration method. The Wikipedia article has more details, including a Python implementation.

The power iteration method requires only taking matrix-vector products, and so remains efficient for large, sparse matrices. Note though that it will find the largest-magnitude eigenvalue and its corresponding eigenvector (and will have numerical issues if the spectral gap between the two largest-magnitude eigenvalues is small); if you want the most-positive eigenvalue of an indefinite matrix instead, you will need to modify the algorithm a bit.