CODEWITHSUNDEEP
pythonalgorithmmatlabmatheigenvalue
Luqman Saleem
Luqman Saleem

Reputation: 183

Can we calculate only the n-th eigenvalue and eigenvector of a very large sparse matrix?

I have a very big sparse matrix A = 7Mi-by-7Mi matrix. I am using Matlab's eigs(A,k) function which can calculate first k eigenvalues and vectors. I need all of its eigenvector and values. But I can't store all of the eigenvectors because it requires a lot of memory.

Is there any way (in Matlab or Python) by which I can get eigenvectors one by one in a for loop? i.e. in ith iteration, I get the ith eigenvector and value.

Upvotes: 4

Views: 1319

Answers (1)

Juan Carlos Ramirez
Juan Carlos Ramirez

Reputation: 2129

If you have a good guess about how large the eigenvalue you are looking for is, say lambda_guess, you can use the Power iteration on 

(A - lambda_guess* Id)^-1

This approach is sometimes referred to as the inverse-shift method. Here the method will converge to the eigenvalue closest to lambda_guess (and the better your guess the faster the convergence). Note that you wouldn't store the inverse, but only compute the solution of

x_next_iter = solve(A - lambda_guess*Id, x_iter), possibly itself with an iterative linear solver.

I would combine this with a subspace iteration method with subspace at least size two. This way, on your first iteration, you can find the smallest and second smallest eigenvalues lambda1, lambda2.

Then you can try lambdaguess= lambda2+ epsilon so that The first and second eigenvector outputted correspond to the second and third smallest eigenvalues, respectively.(if the first eigenvalue of this iteration is not the same as the value of lambda2 for your previous iteration, you need to make epsilon smaller and repeat. In practice you would test that their difference is small enough, to account for roundoff error and the fact that iterative methods are never exact). You repeat this until you get the eigenvalue number you are looking for. It's going to be slow, but you will only use two eigenvectors at any time.

NOTE: we assume all eigenvalues are distinct, otherwise this problem will not have a low memory solution with the usual techniques. In general, if the maximal multiplicity of an eigenvalue is m, you would need m vectors in memory for subspace iteration to converge.

Upvotes: 1

Related Questions