eigen value problem for sparse matrices

Hi, I need to calculate all eigen values and eigen vectors of a very large sparse matrix(above 20k*20k) but an out of memory error will occure! how can I overcome this problem? thank you.

[Matt J]

What are you going to use the eigenvectors/values for?

And how much memory do you have? 20k x 20k isn't all that large. Only 3GB.

[KSSV]

Have a look on eigs.

[amirhossein amirabadi]

I need it for a monte carlo simulation, I want it for the formula in the image.

[amirhossein amirabadi]

eigs not working

[Matt J]

I want it for the formula in the image.

What are the different variables in the formula that you've shown (alpha, beta, psi, etc...)? How are they related to the eigenvalues/vectors.

[amirhossein amirabadi]

psi is the eigen vector, alpha and beta are two members of the eigenvector and lambda is the eigenvalue

[amirhossein amirabadi]

and by the way I find a way to solve my problem, I figured that only small eigenvalues(and corresponding eigenvectors) are needed. so I used eigs for 1000 eigenvalues: eigs(my matrix,1000,'sm') thank you for your attention matt j.

[Andrew Knyazev]

If the matrix is real symmetric or Hermitian, you may also want to try https://www.mathworks.com/matlabcentral/fileexchange/48-lobpcg-m

Answer 1

[Matt J]

Just use

   eig(full(yourMatrix))

[amirhossein amirabadi]

I already used this, but its not working. out of memory!!!!!!!

[Matt J]

How much memory do you have!!!!!

You could try converting your matrix to single (full) type to conserve some memory.

eig(single(full(yourMatrix)) ,'vector');

The calculations will suffer accuracy loss, but maybe not too much, since the input is sparse.

[amirhossein amirabadi]

8Gb,my matrices are above 200k*200k not 20k*20k, ;)

[amirhossein amirabadi]

I tried single and it worked for one case(270k*270k), but by encrease the size of matrix(for example 350k), out of memory came again! my english is not very good I am sorry, thanks for your attention

[amirhossein amirabadi]

I tried this kinds of solutions before, I seeking for an algorithm to calcualate eigen values/vectors one by one, because I only need two members of the each eigen vectors! but eig and eigs give all of them. if I can calculate eigen vectors one by one, I save two members that I need, then clearing the others can save lots of memory.

Answer 2

[Christine Tobler]

The problem is that the eigenvectors of a sparse matrix are dense (in all practically relevant cases), so to store them would require 3GB. Additionally, the algorithm requires some workspace, which will also be several GB.

One thing you can try is to use the 'vector' option, which saves memory because the eigenvalues are returned as a vector instead of a diagonal matrix (will need 3GB less memory):

[U, D] = eig(full(yourMatrix), 'vector');

I tried on my computer with this formula, and it took about 10GB of memory (and ran for 8 minutes), so you'll need a machine with more than this to compute all eigenvalues and eigenvectors of this matrix.

Note I'm assuming your matrix is symmetric; a non-symmetric matrix may require more memory than this.

[amirhossein amirabadi]

Hi, thank you for your attention, yes my matrices are symmetric and also hermitian,

[amirhossein amirabadi]

I tried this kinds of solutions before, I seeking for an algorithm to calcualate eigen values/vectors one by one, because I only need two members of the each eigen vectors! but eig and eigs give all of them. if I can calculate eigen vectors one by one, I save two members that I need, then clearing the others can save lots of memory.

Answer 3

[Christine Tobler]

There aren't any practical algorithms for computing eigenvalues one by one. You can compute a subset of eigenvalues around a given value using eigs (assuming that you can solve a linear system with your matrix without going out of memory). This way, you could run through the spectrum of the matrix, and try to get all the eigenvalues, but this is quite a messy approach.

If the matrix is too large to solve a linear system with in memory, there is no way to compute anything except a set of its extreme eigenvalues using eig and eigs in MATLAB.

There are some iterative methods available that, instead of solving a linear system, would require a preconditioner (a matrix that is very similar to the inverse of the original matrix, but can be applied more quickly). It's typically quite tricky to find a good preconditioner, and very dependent on the structure of the matrix coming in.

[amirhossein amirabadi]

I know that there is no algorithm for computing eigenvalues one by one and my problem is not about eigenvalues, its about eigenvectors, eig and eigs give eigenvectors together in a matrix in the same size of the original one and it cost lots of memory. if an algorithm exists that capable to calculate the eigenvectors by using the corresponding eigenvalues(eigenvalues can be reached by eig or eigs) it would be very helpful. as I said I only need two members of each eigenvector and if I can reach eigenvectors one by one, after calculating one of them I save that two members and clear the others and then I go after the next one and ... . thank you by the way.

[Christine Tobler]

So if you have enough memory to compute all the eigenvalues (can you really do this for your 350k problem?), you could use the fact that A*x - d*x = 0, and solve the linear system (A - d*I) * x = 0. This has the problem that the matrix on the left-hand side matrix is singular - but you can instead choose a number a bit off from d, (maybe 1e-5? Depends on the other sizes), and calling eigs to compute the closest few eigenvalues and eigenvectors to that shift.

This will not be cheap, because the shifted matrix A - d*I has to be factorized for each shift, but it does compute each eigenvector separately (assuming that you can factorize A - d*I i memory|.