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:

Status badges

Description (last modified by 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

Attachments (4)

trac_11274-cache-indefinite-factors-v1.patch (8.1 KB) - added by rbeezer 9 years ago.
trac_11274-exact-cholesky-draft1.patch (8.7 KB) - added by rbeezer 9 years ago.
Safe-keeping
trac_11274-exact-cholesky-v1.patch (13.7 KB) - added by rbeezer 9 years ago.
trac_11274-exact-cholesky-two-by-two.patch (1.9 KB) - added by rbeezer 9 years ago.

Download all attachments as: .zip

Change History (12)

Changed 9 years ago by rbeezer

Changed 9 years ago by rbeezer

Safe-keeping

comment:1 Changed 9 years ago by rbeezer

  • Authors set to Rob Beezer
  • 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.

Changed 9 years ago by rbeezer

comment:3 Changed 9 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 9 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

Changed 9 years ago by rbeezer

comment:5 Changed 9 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 9 years ago by rbeezer

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

comment:7 Changed 9 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 9 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.