2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ You could use the data structures of scipy.sparse and the methods from scipy.sparse.linalg. $\endgroup$ Aug 2, 2021 at 7:53
  • $\begingroup$ What does transition matrix mean in your context? Is it a transition matrix from one basis to another basis or is a left/right stochastic matrix? $\endgroup$ Aug 4, 2021 at 12:48

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.