Opened 11 years ago

Closed 10 years ago

Cholesky matrix decomposition breaks over the rationals

Reported by: Owned by: rbeezer jason, was minor sage-5.1 linear algebra sd40.5 ddrake, novoselt sage-5.1.beta5 Rob Beezer Dan Drake N/A #12966, #13018

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`.

Depends: #12966, #13018

Apply:

Safe-keeping

comment:1 Changed 10 years ago by rbeezer

• Authors set to Rob Beezer
• Dependencies set to #12966, #13018
• Description modified (diff)
• 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:3 Changed 10 years ago by rbeezer

• 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 10 years ago by ddrake

• 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

comment:5 Changed 10 years ago by rbeezer

• 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 10 years ago by rbeezer

• Description modified (diff)
• Status changed from needs_work to needs_review

comment:7 Changed 10 years ago by ddrake

• 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 10 years ago by jdemeyer

• Merged in set to sage-5.1.beta5
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.