Cholesky matrix decomposition breaks over the rationals

[rbeezer]

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:

1. trac_11274-cache-indefinite-factors-v1.patch​
2. trac_11274-exact-cholesky-v1.patch​
3. trac_11274-exact-cholesky-two-by-two.patch​

[rbeezer]

Safe-keeping

[rbeezer]

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

[ddrake]

Positive review to attachment:trac_11274-cache-indefinite-factors-v1.patch​.

[rbeezer]

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

[ddrake]

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

[rbeezer]

"two-by-two" patch adds the motivational 2 x 2 example and fixed three doctest formatting mistakes.

[ddrake]

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