# How to calculate ALL of the eigenvalues/eigenvectors of a large, sparse, asymmetric matrix?

I am trying to calculate all of the eigenvectors/eigenvalues of large (40000x40000), sparse, asymmetric matrix. I am using MATLAB and have 3 GB of working memory. The way I am calculating them is by sweeping through (as suggested here -http://www.mathworks.com/support/solutions/en/data/1-A0QRGR/index.html?product=SL&solution=1-A0QRGR). All of my eigenvalues are negative. I start from near the most negative eigenvalue, use eigs, then select the maximum. I repeat eigs on that maximum plus 1E-5 to avoid using eigs with a shift equal to an eigenvalue and then collect the eigenvalues (and the corresponding eigenvectors) that are greater than that maximum plus 1E-14 to avoid duplicate eigenvalues due to numerical error. I repeat this until the maximum of a new set of eigenvalues reaches close to 0. However, I always seem to fall a few (~5) eigenvalues short of the total. I have checked for the possibility of a maximum being a complex number and making sure that the complex conjugate has been tabulated, but that does not do anything. Moreover, some (~2) of the zero eigenvalues have corresponding eigenvectors that are entirely NaN. I am currently at a complete loss of how to proceed, and any suggestions regarding useful texts, etc., would be greatly appreciated.

• I generally consider a problem of your size intractable (unless you have access to code of academic research-grade algorithms and also a supercomputer). I would like to ask why you need to compute ALL of the eigenpairs, and what is the application of this? – Victor Liu Aug 5 '13 at 18:54
• You have $1.6\cdot 10^9$ matrix elements, which requires 12.8GB to store just the matrix. Regardless of the algorithm you choose, it will not yield any results in any reasonable amount of time if you can't even store the matrix in memory. I agree with Victor that it is impossible in practical terms to compute all eigenvalues of such a matrix. – Wolfgang Bangerth Aug 5 '13 at 20:12
• I am working on a simple Master equation (link) in which the transition matrix contains rate constants do not change in time. I have calculated the rate matrix, which is ~40000x40000. I would like to apply this rate matrix to some initial population vector and look at the time evolution. This can be calculated exactly by calculating the eigenvalues/eigenvectors of the rate matrix. Using the algorithm I described, I can recapitulate the calculation for a smaller rate matrix for which the eigenpairs can be calculated exactly. – Kapil Aug 5 '13 at 21:35
• Why should it be intractable? Using the algorithm described above, it takes ~2 hrs to calculate (nearly) all of the eigen-pairs. – Kapil Aug 5 '13 at 21:40
• If the matrix is sparse, why does it require so much storage for the eigenvalues? (The eigenvectors, if not sparse, are another matter.) There's nothing in the problem statement that doesn't permit the input A(i,j)=-\delta_{i,j}+0.001*\delta_{i,j+1}, although I recognize that this is a stupid case. – Jeff Aug 6 '13 at 2:16