MATLAB: 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)

eigeigs

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.

Best Answer

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?

Related Solutions

MATLAB: Does the function chol correctly indicates that a Matrix is positive definite

For the 10 millionth time, det is a bad way to check is a matrix is singular. (Not your fault for asking though.) In fact, it is NEVER a good way to do so, except in homework, where teachers love to tell you to use det, but not explain why det is bad so often. Sadly, that propagates, because their students will do the same thing. And if nobody ever tells you, then your potential students would learn the same fallacies.

Next, giving us a matrix of elements that are only written in 9 decimal digits of precision for a matrix of doubles tells us nothing.

You are confusing the use of chol to test for a positive definite matrix, with testing for singularity. As well, the matrix you have shown is not even symmetric. That tells me it will usually have complex eigenvalues.

I am a bit surprised that chol does not test to see if the metrix is symmetric. But it looks as if chol only uses the upper triangle of the input array. We can verify that by the following test:

[R,P] = chol(A);
A - R'*R
ans =
 1.1102e-16   5.5511e-17   1.1102e-16   1.1102e-16
   0.063614            0   6.9389e-18   6.9389e-18
    0.14454       0.7565            0            0
   -0.51385      0.92378     0.084864            0

So chol is indeed only looking at the upper triangle. (I think that chol used to test for symmetry too. So that may have changed in some recent release.)

If you want to test to see if A is SINGULAR, NEVER use det. Chol is completely inappropriate too.

rank(A)
ans =
     3

A non-singular 4x4 matrix would have a rank of 4. So A is rank deficient.

Understanding the SVD would be even better for some people, but rank is perfectly adequate in this respect.

MATLAB: Upper and lower bounds of eigenvalues for a 2 by 2 matrix

A simple scheme to give bounds on the eigenvalues:

https://en.wikipedia.org/wiki/Gershgorin_circle_theorem

For a 2x2 matrix, [a,b;c,d], this would yield bounds on the real line as:

min(a - abs(b),d - abs(c))
max(a + abs(b),d + abs(c))

As a test, I'll create a symmetric matrix A so the eigenvalues are known to be real.

A = randn(2,2)*1000; A = (A + A')/2
A =
       196.68       1173.7
       1173.7      -579.06
[a,b,c,d] = deal(A(1,1),A(1,2),A(2,1),A(2,2));
min(a - abs(b),d - abs(c))
ans =
      -1752.8
max(a + abs(b),d + abs(c))
ans =
       1370.4
eig(A)
ans =
      -1427.3
       1044.9

Best Answer

Related Solutions

MATLAB: Does the function chol correctly indicates that a Matrix is positive definite

MATLAB: Upper and lower bounds of eigenvalues for a 2 by 2 matrix

Related Question