Hi! How to decrease the computation time of calculating eigenvalues and eigenvectors of large sparse matrices like 10000X10000(I need all the eigenvalues so I can't use eigs)?
10 次查看(过去 30 天)
显示 更早的评论
I need to find all the eigenvalues of a large matrix which is 10000X10000, and I have to loop it for some 1000 times.My computer has sufficient memory, the problem is it's taking too much time. It is taking 1min or so to calculate the eigenvalues for one time. I cannot use parallel computing because I will go to the next loop based on the eigenvalues I got in the previous loop. But I know the nature of the eigenvalues that I get. The eigenvalues are symmetric(This may not be the proper term) what I mean is for example 2, -2, 1, -1, 2+3i, -2-3i, 3.5, -3.5. So is there any way I could make use of this information to run my code faster?
Thanks in advance.
4 个评论
采纳的回答
John D'Errico
2018-1-17
The simple answer is, I doubt it. But that might not be the complete answer, or even the correct one. And see that any answer that requires any significant amount of computation on the matrix will probably slow down things enough that just calling eig on the complete matrix will be faster. Regardless, it is worth a bit of thought.
But your question reduces to computing the roots of the characteristic polynomial, IF you knew that all of the roots were duplicates, but with a sign difference. So if lambda is a root, then so is -lambda.
In that case, you could write your polynomial in the form
(x - lambda1)*(x + lambda1)*(x - lambda2)*(x + lambda2)* ...
Of course, this reduces to
(x^1 - lambda1^2)*(x^2 - lambda2^2)* ...
Essentially your polynomial will have ALL even powers of x, and ONLY even powers of x. If there are any odd powers at all with non-zero coefficients, then your claim about the roots fails completely.
But if you do have only those even powers, then there is a simple transformation available. Just use y=x^2. So create a new polynomial where you divide all the even powers by 2. This new polynomial will be of lower degree than the original, just as if you were able to turn a 10kx10k matrix into a 5kx5k matrix. Compute the roots, and take the square root, apply a +/- to that root, and you are done.
Note this is not equivalent to computing the eigenvalues of A*A. See that A*A will not only be far less sparse than is A, but A*A will still be of the same size as is A. If A has the desired property of signed symmetric eigenvalues, then A*A will have eigenvalues of multiplicity 2.
The problem is, knowing only that the characteristic polynomial must be of the form that it only has even powers of lambda is not sufficient to determine the patterning of your matrix, or for me to know how to reduce your matrix to one of half the size. This must be the case, since there are lots of matrices which will result in the same characteristic polynomial. However, it may be the case that you know some factor of importance here that you are not telling us. For example, how is it that you know your matrix has eigenvalues with the property that you claim it does?
12 个评论
John D'Errico
2018-1-21
The answer is not obvious to me at the moment, but I have a funny feeling it will be clear at some point. Perhaps the approach Christine took would get you there? Thus, given the matrix
A = [0,B;C,D]
Assume a solution exists of the form
A*[x;y] = lambda*[x;y]
Then we have two equations:
B*y = lambda*x
C*x + D*y = lambda*y
For any non-zero scalar lambda, we can now eliminate x simply as
x = B*y/lambda
So for non-zero lambda, the problem reduces to an expression that looks vaguely like a generalized eigenvalue problem.
(C*B)*y = (lambda^2*I - lambda*D)*y
where I is an nxn identity of the same size as D. Of course, when D was the zero matrix, things got simple before.
While this looks promising, it has one major problem. A standard trick is to complete the square on the right hand side. So, add D*D/4*y to both sides...
(C*B + D*D/4)*y = (lambda^2*I - lambda*D + D*D/4)*y
(C*B + D*D/4)*y = (lambda*I - D/2)^2 * y
But at the moment I don't see this yielding a solution yet, as it still is not either a generalized eigenvalue problem, nor a standard eigenvalue problem.
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!