search

Hipparchus-Math / hipparchus

An efficient, general-purpose mathematics components library in the Java programming language
Apache License 2.0
142 stars 41 forks source link

EigenDecomposition with small matrix entries giving unexpected zeroes #252

Open afossa opened 1 year ago

afossa commented 1 year ago

The eigen-decomposition of symmetric, positive definite matrices should return real and strictly positive eigenvalues.

However, if the matrix has (very?) small entries, some eigenvalues are rounded to 0.0, even after setting epsilon=0.0 in the EigenDecomposition class constructor. This is in contrast with the results provided by implementations such as Matrix.EVD in SMILE or eig in MATLAB which correctly return positive eigenvalues.

Example with a 6x6 matrix:

Hipparchus 1.6345155367040014e-05 1.1026825667505243e-07 2.7548481451847817e-08 1.4945398700162820e-11 0.0000000000000000e+00 0.0000000000000000e+00
SMILE      1.6345155367040017e-05 1.1026825667504563e-07 2.7548481451847437e-08 1.4945398700378445e-11 2.0647209186968416e-21 1.8337646658331150e-22
MATLAB     1.6345155367040000e-05 1.1026825667504600e-07 2.7548481451848700e-08 1.4945398700197100e-11 2.0751061553057500e-21 1.9409437480416100e-22

I attach the code snippet, input matrix and MATLAB output with which I generated the above numbers. eigen-issue.zip

maisonobe commented 1 year ago

I am not sure we can improve this. The problem is not related to the eigenvalues themselves, but rather to the the ratio between the smallest and largest eigenvalues which is about 8.4e16. Scaling the matrix up by 1e10 and the eigenvalues down by 1e10 and setting the epsilon to 1e-20 helped slightly as it allowed to get the fifth eigenvalue, by the last one was still missing. The matrix is ill-conditioned.