Bug 608 - LDLT incorrectly identifies non-positive-semi-definite matrix as positive
LDLT incorrectly identifies non-positive-semi-definite matrix as positive
Status: RESOLVED FIXED
Product: Eigen
Classification: Unclassified
Component: Cholesky
3.1
All All
: Normal Unknown
Assigned To: Nobody
:
Depends on:
Blocks: 3.2
  Show dependency treegraph
 
Reported: 2013-06-05 16:08 UTC by Charles Collicutt
Modified: 2013-10-31 12:25 UTC (History)
2 users (show)



Attachments
Example of a non-positive-semi-definite matrix being misidentified as positive semi-definite. (372 bytes, text/x-c++src)
2013-06-05 16:08 UTC, Charles Collicutt
no flags Details
A tentative fix (8.12 KB, patch)
2013-06-05 18:10 UTC, Gael Guennebaud
no flags Details | Diff

Description Charles Collicutt 2013-06-05 16:08:37 UTC
Created attachment 340 [details]
Example of a non-positive-semi-definite matrix being misidentified as positive semi-definite.

The following matrix is not positive semi-definite:

1 2
2 1

It's an example matrix from the Wikipedia page on positive definiteness: http://en.wikipedia.org/wiki/Positive-definite_matrix

However, Eigen thinks it is positive semi-definite. See attached code example, in which Eigen::LDLT::isPositive() returns true.
Comment 1 Gael Guennebaud 2013-06-05 17:47:48 UTC
Right. I think that the fix consists in updating the sign after the diagonal coefficient mat(k,k) has been computed.
Comment 2 Gael Guennebaud 2013-06-05 18:10:20 UTC
Created attachment 341 [details]
A tentative fix

Here is a tentative patch. Please comment.
Comment 3 Gael Guennebaud 2013-06-09 23:34:48 UTC
https://bitbucket.org/eigen/eigen/commits/7df582d9b7d1/
Changeset:   7df582d9b7d1
User:        ggael
Date:        2013-06-09 23:19:32
Summary:     Fix bug 608: the sign computation in LDLT was broken

https://bitbucket.org/eigen/eigen/commits/a4d339217b38/
Changeset:   a4d339217b38
User:        ggael
Date:        2013-06-09 23:30:04
Summary:     Add regression test for bug 608

https://bitbucket.org/eigen/eigen/commits/e5cf0ff732ea/
Changeset:   e5cf0ff732ea
Branch:      3.1
User:        ggael
Date:        2013-06-09 23:19:32
Summary:     Fix bug 608: the sign computation in LDLT was broken
(transplanted from 7df582d9b7d1986c1db1e4dadfe20581f38b5adb)
Comment 4 Charles Collicutt 2013-10-31 10:27:28 UTC
This fix has been applied to the 3.1 branch (and it works, thank you!) but it has not been applied to 3.2. We recently upgraded to 3.2 and found that we now have the same issue again. Any chance it could be applied to 3.2 as well?
Comment 5 Christoph Hertzberg 2013-10-31 10:43:35 UTC
The fix was applied before 3.2 was branched. Which 3.2 version are you using (released tar-ball, or latest hg)? Can you give a matrix, which fails in 3.2?
Comment 6 Charles Collicutt 2013-10-31 12:25:29 UTC
Oops. We did upgrade to 3.2 but then someone inadvertently reverted the upgrade. It's actually fine, sorry.

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