New user self-registration is currently disabled. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Bug 933 - EigenSolver provided the wrong result for some input values
EigenSolver provided the wrong result for some input values
Status: RESOLVED FIXED
Product: Eigen
Classification: Unclassified
Component: Eigenvalues
3.2
x86 - 64-bit Windows
: Normal Wrong Result
Assigned To: Nobody
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2015-01-21 23:41 UTC by Carl
Modified: 2015-01-28 16:09 UTC (History)
4 users (show)



Attachments
Code that generated the above output (1.30 KB, text/plain)
2015-01-21 23:41 UTC, Carl
no flags Details

Description Carl 2015-01-21 23:41:32 UTC
Created attachment 521 [details]
Code that generated the above output

I implemented a function to find the zeros of an n-degree polynomial which finds the eigenvalues of the companion matrix of the polynomial coefficients.  I tested it with a manufactured 4th degree polynomial and it worked exactly as expected.  However, when I used the polynomial coefficients that I really need to factor in my larger algorithm, it fails to find two of the zeros.  The eigenvalues (D) and eigenvectors (V) returned from the EigenSolver class are not correct in that EigenSolver es(A), D=es.eigenvalues().asDiagonal(), V=es.eigenvectors(), A != V * D * V.inverse().  I've attached my function and a test driver that shows the EigenSolver returning the correct values and then returning the incorrect values simply based on the input.

Visual C++ 2013 Output
**********************************
Polynomial coefficients =    1   -3 -175 -225 2250
The Companion Matrix:
    3   175   225 -2250
    1     0     0     0
    0     1     0     0
    0     0     1     0
Eigen Values =
 (15,0)   (0,0)   (0,0)   (0,0)
  (0,0) (-10,0)   (0,0)   (0,0)
  (0,0)   (0,0)  (-5,0)   (0,0)
  (0,0)   (0,0)   (0,0)   (3,0)
Eigen Vectors =
   (-0.997775,0)     (0.994987,0)     (0.979797,0)    (-0.942881,0)
  (-0.0665184,0)   (-0.0994987,0)    (-0.195959,0)    (-0.314294,0)
 (-0.00443456,0)   (0.00994987,0)    (0.0391919,0)    (-0.104765,0)
(-0.000295637,0) (-0.000994987,0)  (-0.00783838,0)   (-0.0349215,0)
V * D * V.inverse() =
            (3,0)           (175,0)           (225,0)         (-2250,0)
            (1,0) (-6.53781e-015,0) (-3.55271e-014,0) (-1.52767e-013,0)
  (5.9848e-017,0)             (1,0) (-4.21885e-015,0)  (1.06581e-014,0)
 (6.50521e-018,0) (-5.95185e-017,0)             (1,0) (-1.11022e-015,0)

Polynomial coefficients =  6.15467e-015 -1.00387e-010     -0.981957       3995.72  2.21151e+008
The Companion Matrix:
      16310.7  1.59547e+014 -6.49217e+017 -3.59322e+022
            1             0             0             0
            0             1             0             0
            0             0             1             0
Eigen Values =
(1.26393e+007,0)            (0,0)            (0,0)            (0,0)
           (0,0) (-1.2623e+007,0)            (0,0)            (0,0)
           (0,0)            (0,0)            (0,0)            (0,0)
           (0,0)            (0,0)            (0,0)            (0,0)
Eigen Vectors =
           (1,0)           (-1,0) (-1.9664e-009,0)            (0,0)
(7.91181e-008,0) (7.92203e-008,0)            (1,0)            (1,0)
           (0,0)            (0,0)  (0.000245753,0)            (0,0)
           (0,0)            (0,0)            (0,0) (4.44021e-009,0)
V * D * V.inverse() =
      (16310.7,0)  (1.59547e+014,0) (-6.49217e+017,0) (-3.59322e+022,0)
            (1,0)  (9.31323e-010,0)  (7.62939e-006,0)         (-0.25,0)
            (0,0)             (0,0)             (0,0)             (0,0)
            (0,0)             (0,0)             (0,0)             (0,0)

*********************************************************************************			
Matlab Eigenvalues =  12637292.040755 -12625050.466347 17179.011261 -13109.889609
Comment 1 Carl 2015-01-22 19:45:08 UTC
As an update...
The companion matrix is already in upper Hessenberg form so I only have to do a Schur decomposition to get the eigenvalues.  The Eigen::RealSchur decomposition is the one that fails to produce all of the eigenvalues.  I ran it with the Eigen::ComplexSchur decomposition and got all of the eigenvalues.  I have not been able to determine why the Eigen::RealSchur fails while the Eigen::ComplexSchur succeeds.
Comment 2 Gael Guennebaud 2015-01-28 16:09:44 UTC
Thank you for the precise report.

https://bitbucket.org/eigen/eigen/commits/c90f5b999226/
Changeset:   c90f5b999226
User:        ggael
Date:        2015-01-28 15:07:51+00:00
Summary:     Bug 933: RealSchur, do not consider the input matrix norm to check negligible sub-diag entries. This also makes this test consistent with the complex and self-adjoint cases.

3.2 backport:
https://bitbucket.org/eigen/eigen/commits/497287cda9c9/

Note You need to log in before you can comment on or make changes to this bug.