I have a problem in hand that involves calculation of eigenvector of a large sparse matrix ($10^7 \times 10^7$). A first-order Markov chain is fit to the problem, and the state transition probability matrix has only 7 non-zero entries at each column. I used power method and Rayleigh quotient method to quickly calculate the steady state occupancy distribution, and finally MATLAB's eigs function with the option to return only the largest eigen pair.
Apart from which method is more efficient and all that, even the construction of the state transition probability matrix takes some time. Numerical analysis is not my field, but I was wondering if the the following facts can help me to improve the calculation speed:
- I'm only interested in eigenvector corresponding to the largest eigenvalue (which is obviously 1)
- the non-zero entries of the matrix can be calculated on the fly, I mean there is routine $f$ which $p_{ij} = f(i, j)$, $\text{P}=[p_{ij}]$ is the state transition probability matrix.
Any help/reference is much appreciated.
In this case the Arnoldi iteration method for calculating eigenvalues (i.e. the method used by eigs function) will probably be the fastest method to find stationary distribution.
You need to have an efficient method for forming a sparse-dense multiplication $Av$ many times for different $v$. If the matrix $A$ does not have any special structure, that can speed up forming $Av$, then you need to costruct this matrix explicitly. Calculating elements of $A$ on the fly will only slow down computations considerably, since all elements of $A$ will be recalculated many times.