Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
roundoff error in eig for symmetric A

Subject: roundoff error in eig for symmetric A

From: Henry Wolkowicz

Date: 8 Aug, 2011 20:27:10

Message: 1 of 9

I used eig [V,D]=eig(full((A+A')/2)), where A is a random sparse, SYMMETRIC, order=1000, it has multiple eigenvalues. Then norm(A*V-V*D) was very large ... order 8.5. Several elements in (A*V-V*D) was order 1. I ran this many times and the large error only occured perhaps 1/10 of the tests. Most times the error was 'tiny'. This error seems 'huge'. Is this to be expected?

Subject: roundoff error in eig for symmetric A

From: Henry Wolkowicz

Date: 9 Aug, 2011 21:15:31

Message: 2 of 9

"Henry Wolkowicz" wrote in message <j1pgqu$oof$1@newscl01ah.mathworks.com>...
> I used eig [V,D]=eig(full((A+A')/2)), where A is a random sparse, SYMMETRIC, order=1000, it has multiple eigenvalues. Then norm(A*V-V*D) was very large ... order 8.5. Several elements in (A*V-V*D) was order 1. I ran this many times and the large error only occured perhaps 1/10 of the tests. Most times the error was 'tiny'. This error seems 'huge'. Is this to be expected?
-----------------------------------------------------------
I am continuing to test both eig and eigs to find the smallest eigenvalue (and eigenvector) and I am having lots of problems. The smallest eigenvalue is not a 'singleton', i.e. is a multiple eigenvalue. I am getting the second largest using eigs
eigs(Ahandle,n,1,'SA',OPTIONS) The problem is NOT huge, just n=100 but the smallest eigenvalue has multiplicity 5. Are other people having such serious problems with eigs and eig?

Subject: roundoff error in eig for symmetric A

From: Bruno Luong

Date: 9 Aug, 2011 21:25:30

Message: 3 of 9

Never use EIGS for more than very few eigen values. This algorithm is not stable, it is well known fact.

EIG is better. But I wouldn't bet the money on it either.

Bruno

Subject: roundoff error in eig for symmetric A

From: Henry Wolkowicz

Date: 9 Aug, 2011 21:56:28

Message: 4 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <j1s8ka$q6i$1@newscl01ah.mathworks.com>...
> Never use EIGS for more than very few eigen values. This algorithm is not stable, it is well known fact.
>
> EIG is better. But I wouldn't bet the money on it either.
>
> Bruno

Thanks for the reply!! I agree. It is so easy to not get the smallest eigenvalue when using eigs and you are of course trying for the smallest (A is symmetric). flag=0 indicates that the algorithm converged but it seems to converge to the wrong eigenvalue. We had to change OPT.v0 several times to avoid the bad convergence.
Also, we found one very bad example for eig From books I read that the symmetric eigenvalue problem has 'condition number 1'. But I get essentially garbage for this symmetric eigenvalue problem. Is there a more robust code around than eigs/eig?
thanks again. (I can post the mat file for the eig problem)

Subject: roundoff error in eig for symmetric A

From: Bruno Luong

Date: 9 Aug, 2011 22:10:28

Message: 5 of 9


> Thanks for the reply!! I agree. It is so easy to not get the smallest eigenvalue when using eigs and you are of course trying for the smallest (A is symmetric). flag=0 indicates that the algorithm converged but it seems to converge to the wrong eigenvalue. We had to change OPT.v0 several times to avoid the bad convergence.

EIGS is based on Lanczos/Arnoldi algorithm, and it's unstable as we already know.

> Also, we found one very bad example for eig From books I read that the symmetric eigenvalue problem has 'condition number 1'.

That's right. The symmetric matrix has orthonormal eigen basis, thus condition number (for eigen value) = 1. Still for large matrix, the round off error can still accumulate, and has non negligible impact, even with perfect condition numbers.
 
> But I get essentially garbage for this symmetric eigenvalue problem. Is there a more robust code around than eigs/eig?

I don't know all existing algorithms. Though human kind has yet to find a perfect algorithm for eigen value problems, the last time I check.

Bruno

Subject: roundoff error in eig for symmetric A

From: Matt J

Date: 10 Aug, 2011 02:28:29

Message: 6 of 9

"Henry Wolkowicz" wrote in message <j1pgqu$oof$1@newscl01ah.mathworks.com>...
> I used eig [V,D]=eig(full((A+A')/2)), where A is a random sparse, SYMMETRIC, order=1000, it has multiple eigenvalues. Then norm(A*V-V*D) was very large ... order 8.5. Several elements in (A*V-V*D) was order 1. I ran this many times and the large error only occured perhaps 1/10 of the tests. Most times the error was 'tiny'. This error seems 'huge'. Is this to be expected?
====================

Are you sure A is symmetric? If A is already symmetric, why is it necessary to do
(A+A')/2?

When A is not symmetric, I see errors of this order, but not otherwise.

Subject: roundoff error in eig for symmetric A

From: Henry Wolkowicz

Date: 10 Aug, 2011 08:01:13

Message: 7 of 9

"Matt J" wrote in message <j1sqcd$gc6$1@newscl01ah.mathworks.com>...
> "Henry Wolkowicz" wrote in message <j1pgqu$oof$1@newscl01ah.mathworks.com>...
> > I used eig [V,D]=eig(full((A+A')/2)), where A is a random sparse, SYMMETRIC, order=1000, it has multiple eigenvalues. Then norm(A*V-V*D) was very large ... order 8.5. Several elements in (A*V-V*D) was order 1. I ran this many times and the large error only occured perhaps 1/10 of the tests. Most times the error was 'tiny'. This error seems 'huge'. Is this to be expected?
> ====================
>
> Are you sure A is symmetric? If A is already symmetric, why is it necessary to do
> (A+A')/2?
>
> When A is not symmetric, I see errors of this order, but not otherwise.
Yes A was symmetric. But We added the extra (A+A')/2 to ensure that it was symmetric. A is formed in blocks using sprandsym where one of the blocks is
orthog. rotated Q*B*Q'. So the roundoff may cause loss of symmetry. Therefore, we symmetrize above. But the smallest eigenvalue has high multiplicity.

Subject: roundoff error in eig for symmetric A

From: Henry Wolkowicz

Date: 10 Aug, 2011 08:25:10

Message: 8 of 9

"Henry Wolkowicz" wrote in message <j1tds9$ajq$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <j1sqcd$gc6$1@newscl01ah.mathworks.com>...
> > "Henry Wolkowicz" wrote in message <j1pgqu$oof$1@newscl01ah.mathworks.com>...
> > > I used eig [V,D]=eig(full((A+A')/2)), where A is a random sparse, SYMMETRIC, order=1000, it has multiple eigenvalues. Then norm(A*V-V*D) was very large ... order 8.5. Several elements in (A*V-V*D) was order 1. I ran this many times and the large error only occured perhaps 1/10 of the tests. Most times the error was 'tiny'. This error seems 'huge'. Is this to be expected?
> > ====================
> >
> > Are you sure A is symmetric? If A is already symmetric, why is it necessary to do
> > (A+A')/2?
> >
> > When A is not symmetric, I see errors of this order, but not otherwise.
> Yes A was symmetric. But We added the extra (A+A')/2 to ensure that it was symmetric. A is formed in blocks using sprandsym where one of the blocks is
> orthog. rotated Q*B*Q'. So the roundoff may cause loss of symmetry. Therefore, we symmetrize above. But the smallest eigenvalue has high multiplicity.
One more thing: this was with version 2010a I just upgraded to 2011a and that large error does not happen, i.e. I had saved the matrix and now do not get
a large error.

Subject: roundoff error in eig for symmetric A

From: Matt J

Date: 10 Aug, 2011 13:27:11

Message: 9 of 9

"Henry Wolkowicz" wrote in message <j1tds9$ajq$1@newscl01ah.mathworks.com>...
>
> > Are you sure A is symmetric? If A is already symmetric, why is it necessary to do
> > (A+A')/2?
> >
> > When A is not symmetric, I see errors of this order, but not otherwise.
> Yes A was symmetric. But We added the extra (A+A')/2 to ensure that it was symmetric. A is formed in blocks using sprandsym where one of the blocks is
> orthog. rotated Q*B*Q'. So the roundoff may cause loss of symmetry. Therefore, we symmetrize above. But the smallest eigenvalue has high multiplicity.
====================


What about if you do as follows (in R2010a)

M=(A+A')/2;
[V,D]=eig(M);

norm(M*V-V*D),

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us