How should I compute the eigenvectors of a sparse, real, symmetric matrix?

조회 수: 57 (최근 30일)
I need to compute all the eigenvectors of a sparse, real, symmetric matrix, A.
I've tried the following:
>> [V, D] = eig(A);
Error using eig
For standard eigenproblem EIG(A) when A is sparse, EIG does not support computing eigenvectors. Use EIGS instead.
>> [V, D] = eigs(A, size(A, 1));
Warning: For real symmetric problems, must have number of eigenvalues k < n.
Using eig instead.
So MATLAB gives me conflicting advice: first, to use eigs, and then to use eig! What it does internally is convert my sparse matrix to a full one. This seems inefficient if I have lots of sparsity. Any better suggestions?
  댓글 수: 2
Matt J
Matt J 2013년 10월 31일
편집: Matt J 2013년 10월 31일
What it does internally is convert my sparse matrix to a full one.This seems inefficient if I have lots of sparsity.
Why do you think sparsity should have an advantage in eigenvalue computation?
Oliver Woodford
Oliver Woodford 2013년 10월 31일
For the same reasons it has an advantage in other computations.

댓글을 달려면 로그인하십시오.

채택된 답변

Oliver Woodford
Oliver Woodford 2013년 11월 1일
편집: Oliver Woodford 2013년 11월 1일
Just convert the matrix to a full one, and use eig. Unless less you want just a few eigenvectors, then the decomposition using the sparse matrix will generally be slower anyway. E.g.:
>> A = sprand(2e3, 2e3, 2e-3);
>> A = A' + A;
>> tic; [V, D] = eigs(A, 2e3-2); toc;
Elapsed time is 21.727999 seconds.
>> tic; [V, D] = eig(full(A)); toc
Elapsed time is 2.488241 seconds.
Moral of the story: sparse isn't always faster!

추가 답변 (2개)

Matt J
Matt J 2013년 11월 1일
편집: Matt J 2013년 11월 1일
For the same reasons it has an advantage in other computations.
Sparsity just isn't always helpful. You have to know if/why it will be useful in a given situation.
In the case of eigenvalue decomposition, it's hard to see how sparsity could be exploited. Eigendecomposition is based on QR decomposition and the QR decompositions of sparse matrices are not sparse. That could be the reason why qr() is so much slower for sparse matrices, e.g.,
>> As=sprand(3e3,3e3,1e-3); Af=full(As);
>> tic; [Q,R]=qr(Af);toc
Elapsed time is 2.506753 seconds.
>> tic; [Q,R]=qr(As);toc
Elapsed time is 15.731333 seconds.
There are also operations that are slower for MATLAB's sparse type because of software design compromises, even simple transposition:
>> Af=zeros(1e7,1); As=sparse(Af);
>> tic; Af.'; toc
Elapsed time is 0.000012 seconds.
>> tic; As.'; toc
Elapsed time is 0.054525 seconds.
  댓글 수: 5
Matt J
Matt J 2013년 11월 1일
편집: Matt J 2013년 11월 1일
But do you not get my perspective here?
It's an understandable perspective from someone convinced that there was an "implication of fallacy" in my initial comment. However, you could also consider the possibility that I in fact thought you might be right, but that your reasoning was not obvious, and that I was just looking for elaboration...
Why my answer is considered off point, I still don't get. I explained what you eventually concluded yourself in your Answer, that "sparse isn't always faster".
I also don't understand why you decided your question was resolved and closed the thread. Your original question was if/why it's not possible to do better than eig(full(S)). Do you now believe you know why? If so, why is my theory about QR so outlandish? I think we agree that eig() uses QR. If you're now convinced that eig(), and hence QR, is the optimal eigendecomposition method, isn't it relevant that QR won't be faster in sparse form?
Oliver Woodford
Oliver Woodford 2013년 11월 1일
You wouldn't use QR with a sparse matrix, you'd use Lanczos. I don't actually know what eig uses, and I only assume eigs uses Lanczos from what I read online, and looking at the code, after your answer. My reason for originally believing that sparse would be more efficient is that solving linear problems involving sparse matrices generally is, so I was in no position to either provide the answer you were looking for, or indeed verify your answer. Hence suggesting the more straightforward answer. I don't know if one can do better, but it doesn't seem likely in MATLAB.

댓글을 달려면 로그인하십시오.


Matt J
Matt J 2013년 11월 3일
편집: Matt J 2013년 11월 3일
It does appear that the Lanczos algorithm, if that's what is being used by EIGS, is not being used optimally for the case when only the eigenvalues are requested as output. According to here, Lanczos should be able to derive the eigenvalues in O(N^2) for a sparse matrix of density 1/N. However, in my tests below, computation time for the eigenvalues does seem to go cubically with N,
for N=[1:4]*1e3;
A = sprand(N, N, 1/N); A=A+A.';
tic; E = eigs(A, N-1); toc;
end
Elapsed time is 1.124703 seconds.
Elapsed time is 8.516908 seconds.
Elapsed time is 27.762566 seconds.
Elapsed time is 65.062230 seconds.
It might therefore be worth trying some of the external MATLAB Lanczos implementations, also at the link above.
When eigenvectors are requested as well, all bets are off. There is nothing I can see in the Lanczos algorithm that gaurantees less than O(N^3) computation. In particular, the final conversion from Lanczos vectors to eigenvectors would require an NxN matrix multiplication. Also, non-sparse memory allocation is required just to hold the N eigenvectors, so who kows what overhead that will bring. It doesn't appear that Lanczos was meant for doing full eigenvector decomposition, only partial ones.

카테고리

Help CenterFile Exchange에서 Sparse Matrices에 대해 자세히 알아보기

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by