I would like to efficiently and (to the extent possible) reliably find the Perron-Frobenius eigenvector of non-negative matrices. These are not stochastic matrices, they are typically dense, and their entries differ by many orders of magnitude. They are probably usually irreducible, though if you think of the very small entries as zero they will not be. They are not symmetric. They will be as large as I can make them with reasonable computation time on a laptop.
I'm not much of a numerics person and up to now I've tended to treat eigenvector routines as a "back box". However, in this case none of the off-the-shelf solutions I've tried work very well. Numpy's
linalg.eig is very slow for matrices bigger than $2000\times 2000$ or so, presumably because it always computes every eigenvector, not just the top one. Moreover, the eigenvalue with the largest real part often does not correspond to an eigenvector with all non-negative (or even real) entries, which messes everything up. On the other hand,
scipy.sparse.linalg.eigs is great when it works (despite my matrices being dense), but sometimes I just can't get it to converge no matter what I do.
I tried implementing power iteration by myself, but it's very slow and also suffers from convergence issues - it leaves me feeling that there ought really to be a better way.
Ideally I would like an algorithm with the following properties:
- faster than power iteration and with better convergence properties
- able to give me some kind of approximate solution in the case where it can't converge
- guaranteed not to give me any eigenvector other than the Perron-Frobenius one, i.e. not to give me something with complex elements or a mixture of positive and negative ones
- able to compute the left and right Perron-Frobenius eigenvectors simultaneously, if that would be more efficient than simply running it twice
- either available off-the-shelf (in Python or some other language), or explained in a form such that I, as a non-numerics person, can understand how to implement it without worrying too much about the theory behind it
Does such a thing exist? References to literature giving an overview of how to solve this kind of problem would also be welcome, as I'm sure I'm not the first person to need to do this.