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?

  • $\begingroup$ Ten million entries doesn't seem to be too big to fit into memory, unless you are dealing with an ancient computer. $\endgroup$ – Michael Ulm Sep 10 '10 at 8:21
  • 1
    $\begingroup$ Yes, I actually meant 10 billion (fixed). Also, the bigger the feasible size - the better. $\endgroup$ – Gadi A Sep 10 '10 at 9:10
  • 1
    $\begingroup$ Why did this question get duplicated in MO? It only makes it more complicated for people having the same question to find answers! $\endgroup$ – Mariano Suárez-Álvarez Sep 10 '10 at 10:41
  • $\begingroup$ My mistake, won't happen again. Sorry. $\endgroup$ – Gadi A Sep 10 '10 at 11:49

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!

  • 1
    $\begingroup$ +1 ; In short, Arnoldi is the best choice for sparse unsymmetric problems. As long as you have a routine for generating the $(i,j)$ entry of $A$ you should be able to write a matrix-vector multiplication routine that Arnoldi will need. If working in FORTRAN, there's ARPACK: caam.rice.edu/software/ARPACK $\endgroup$ – J. M. isn't a mathematician Sep 10 '10 at 10:12
  • $\begingroup$ If I understand Arnoldi correctly, I still need to store v in the memory; however, my problem is that v itself is too large (around 10 billion entries). My main question is whether it is possible to avoid storing v in the memory (or at least storing only some part of it, etc.) $\endgroup$ – Gadi A Sep 11 '10 at 7:33
  • $\begingroup$ @Gadi: Unfortunately, Arnoldi does require an array to represent the vector. Is $\mathbf{v}$ sparse or dense? I'm thinking maybe conformal partitioning might be of use here. $\endgroup$ – J. M. isn't a mathematician Sep 12 '10 at 9:56

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.


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.


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.