On computing the largest eigenvalue of a very large sparse matrix

Question

I am trying to compute the asymptotic growth-rate in a specific combinatorial problem depending on a parameter w, using the Transfer-Matrix method. This amounts to computing the largest eigenvalue of the corresponding matrix.

For small values of w, the corresponding matrix is small and I can use the so-called power method - start with some vector, and multiply it by the matrix over and over, and under certain conditions you'll get the eigenvector corresponding to the largest eigenvalue. However, for the values of w I'm interested in, the matrix becomes to large, and so the vector becomes too large - $n>10,000,000,000$ entries or so, so it can't be contained in the computer's memory anymore and I need extra programming tricks or a very powerful computer.

As for the matrix itself, I don't need to store it in memory - I can access it as a black box, i.e. given $i,j$ I can return $A_{ij}$ via a simple computation. Also, the matrix has only 0 and 1 entries, and I believe it to be sparse (i.e. only around $\log n$ of the entries are 1's, $n$ being the number of rows/columns). However, the matrix is not symmetric.

Is there some method more space-effective for computation of eigenvalues for a case like this?

Answer 1

You could use the Arnoldi Iteration algorithm. This algorithm only requires the matrix $A$ for matrix-vector multiplication. I'm expecting that you will be able to black-box the function $v\rightarrow Av$. What you generate is an upper Hessenberg matrix $H$ whose eigenvalues whose can be computed cheaply (by a direct method or Rayleigh quotient iteration) and which approximate the eigenvalues of $A$. Arnoldi Iteration will give the best approximation to the dominant eigenvalue so I suspect you won't have to do many iterations before you have a good estimate.

An excellent introduction to this is: "Numerical Linear Algebra" by Trefethen and Bau. (p250)

The basic algorithm can be found here: http://en.wikipedia.org/wiki/Arnoldi_iteration

Now the only thing that is required to make this a fully functional algorithm is a termination condition. Since you don't seem to need the dominant eigenvalue to a high degree of accuracy I would not worry and just stop when the dominant eigenvalue estimate doesn't change too much.

If you have Matlab you can always use the built in function eigs(Afun,n,...) where Afun is the black-box function handle that computes $Av$.

Good luck!

Answer 2

For a computer package that solves the eigenvalue for large sparse matrix problem. Use ARPACK.

For wiki:

The package is designed to compute a few eigenvalues and corresponding eigenvectors of large sparse or structured matrices, using the Implicitly Restarted Arnoldi Method (IRAM) or, in the case of symmetric matrices, the corresponding variant of the Lanczos algorithm.the Lanczos algorithm.

Answer 3

Please search for external memory linear algebra or out of core computation to see if you find implementations / ideas for how to manage these huge 'v' vectors.

Moreover, since computing the largest eigenvalue + corresponding eigenvector are in a way core parts of Google's pagerank algorithm, you might find useful leads on how to perform this huge computation by using ideas similar to those used for pagerank.

Also, if you are content with approximate answers, other options like random projections open up.