Opened 10 years ago
Closed 9 years ago
#11274 closed defect (fixed)
Cholesky matrix decomposition breaks over the rationals
Reported by: | rbeezer | Owned by: | jason, was |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.1 |
Component: | linear algebra | Keywords: | sd40.5 |
Cc: | ddrake, novoselt | Merged in: | sage-5.1.beta5 |
Authors: | Rob Beezer | Reviewers: | Dan Drake |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12966, #13018 | Stopgaps: |
Description (last modified by )
The matrix E is clearly symmetric, and by looking at its eigenvalues and the determinants of principal submatrices it is clearly positive definite.
sage: E = matrix(QQ, [[2, 1], [1, 1]]) sage: E.is_symmetric() True sage: E.eigenvalues() [0.3819660112501051?, 2.618033988749895?] sage: E.det() 1 sage: E.cholesky_decomposition() --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <snip> ValueError: The input matrix was not symmetric and positive definite
At best the error message is misleading.
The try/except block needs to be more careful. It should be checking if square roots are contained in the base ring, or it should first convert to an algebraically closed field, or something like that.
In this example, the error is raised because the square root of a rational is not again a rational, when I think the test should be if the argument to the square root is negative.
Perhaps for QQ
, the base ring should be promoted to the Real Algebraic Field, AA
.
Apply:
Attachments (4)
Change History (12)
Changed 9 years ago by
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Cc ddrake novoselt added
- Dependencies set to #12966, #13018
- Description modified (diff)
- Keywords sd40.5 added
- Caching indefinite factorization seems to be ready to go.
- Exact Cholesky decomposition is working - tested on simple examples, but needs documentation.
- Cholesky overall needs a brutal refactoring, the existing situation is a total mess.
comment:2 Changed 9 years ago by
Positive review to attachment:trac_11274-cache-indefinite-factors-v1.patch.
Changed 9 years ago by
comment:3 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
"v1" patch implements Cholesky decomposition for matrices over exact rings, based on the indefinite factorization routines.
This is named cholesky()
in preparation for its un-deprecation. A total cleanup of the total mess will be the next task/ticket.
comment:4 Changed 9 years ago by
- Reviewers set to Dan Drake
- Status changed from needs_review to positive_review
The exact Cholesky decomposition looks good. The only thing we might want is to add in the example from the description of the ticket (which now works) but the documentation is quite thorough, so it seems very unlikely that the little 2x2 case will fail with the tests we have.
Runtime for random matrices over the rationals is fine; 100x100 matrices finish in about 6.2 seconds on my machine.
Positive review to trac_11274-exact-cholesky-v1.patch.
Apply trac_11274-cache-indefinite-factors-v1.patch and trac_11274-exact-cholesky-v1.patch
Changed 9 years ago by
comment:5 Changed 9 years ago by
- Status changed from positive_review to needs_work
"two-by-two" patch adds the motivational 2 x 2 example and fixed three doctest formatting mistakes.
comment:6 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:7 Changed 9 years ago by
- Status changed from needs_review to positive_review
The extra 2x2 example is nice. Positive review.
Apply trac_11274-cache-indefinite-factors-v1.patch trac_11274-exact-cholesky-v1.patch trac_11274-exact-cholesky-two-by-two.patch
comment:8 Changed 9 years ago by
- Merged in set to sage-5.1.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
Safe-keeping