Opened 10 years ago

Closed 10 years ago

#12966 closed enhancement (fixed)

Indefinite factorization for exact matrices

Reported by: rbeezer Owned by: jason, was
Priority: minor Milestone: sage-5.1
Component: linear algebra Keywords: sd40.5
Cc: Merged in: sage-5.1.beta2
Authors: Rob Beezer Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

Almost any square symmetric (or Hermitian) matrix A over a field can be decomposed into a lower triangular matrix L and a diagonal matrix D such that A = L*D*L-transpose, suitably adjusted in the Hermitian case.

1) This is of interest for its own sake (eg for solving systems).

2) If the field has square roots and the diagonal matrix has positive entries, then the Cholesky decomposition is easy. This would fix #11274.

3) This will give a good way to tell if a matrix is positive definite.

Apply:

  1. trac_12966-indefinite-factorization-v2.patch

Attachments (3)

trac_12966-indefinite-factorization-draft-1.patch (6.5 KB) - added by rbeezer 10 years ago.
trac_12966-indefinite-factorization-v1.patch (15.3 KB) - added by rbeezer 10 years ago.
trac_12966-indefinite-factorization-v2.patch (15.6 KB) - added by rbeezer 10 years ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 10 years ago by rbeezer

Draft 1 patch is mostly for safe-keeping. It "works" but needs an option for failure mode - zero diagonals versus negative diagonals. Underscore method will then be used to address the three items above - (1) on this ticket, (2) on the bug ticket, and (3) somewhere.

comment:2 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from new to needs_review

v1 patch implements general utility function as an underscore method and then uses this for a user-level method. The utility method will be used to provide an is_positive_definite method and a fixed version of Cholesky decomposition.

comment:3 Changed 10 years ago by rbeezer

  • Keywords sd40.5 added

comment:4 Changed 10 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev

Looking over.

comment:5 follow-up: Changed 10 years ago by novoselt

For the documentation:

  • line 10032: Why the base ring for the diagonal matrix is mentioned explicitly? I think the output for d must be such that the appropriate matrix is constructed from d directly.
  • lines 10040-10042: Probably need one more space for perfect alignment.
  • line 10292: I don't understand the reference to RDF/CDF - how can they be used if they are not exact?

Implementation-wise, I don't understand why error-handling is delegated to calling functions - checking for square matrices seems natural before the actual computation, detecting absence of the fraction field seems to be repeated and I don't understand at all what is accomplished by

except ValueError as e: 
    raise ValueError(e)

can't it just be deleted without any effect on the behaviour? It seems to me that the only real work for non-underscore method is to convert d to a vector (which probably addressed my first comment on the documentation). It seems to me that either this can be the only thing left in this function with error-checking going to the underscore method or even the conversion can go there and we end up with a single function.

comment:6 in reply to: ↑ 5 Changed 10 years ago by rbeezer

Replying to novoselt: Andrey,

Thanks for the comments. The underscore method will also power an "is_positive_definite" method and a new (fixed) "cholesky_decompsition" method. I was trying to isolate common functionality in the underscore method. I was also trying to have errors be actually reported out of the calling functions.

In particular, indefinite factorization will fail if there is a zero computed for the diagonal. But this is also an indicator of a non-positive-definite matrix, so I want to catch that error and convert it to a False return. I'm still uncertain about how Cholesky will be employing this routine.

Rob

For the documentation:

  • line 10032: Why the base ring for the diagonal matrix is mentioned explicitly? I think the output for d must be such that the appropriate matrix is constructed from d directly.
  • lines 10040-10042: Probably need one more space for perfect alignment.
  • line 10292: I don't understand the reference to RDF/CDF - how can they be used if they are not exact?

Implementation-wise, I don't understand why error-handling is delegated to calling functions - checking for square matrices seems natural before the actual computation, detecting absence of the fraction field seems to be repeated and I don't understand at all what is accomplished by

except ValueError as e: 
    raise ValueError(e)

can't it just be deleted without any effect on the behaviour? It seems to me that the only real work for non-underscore method is to convert d to a vector (which probably addressed my first comment on the documentation). It seems to me that either this can be the only thing left in this function with error-checking going to the underscore method or even the conversion can go there and we end up with a single function.

comment:7 Changed 10 years ago by novoselt

Well, as I understand is_positive_definite can call the decomposition and return False if either it fails of there are negative entries. For this patch it seems that the purpose of both methods is exactly the same - if the underscore cannot compute the decomposition for whatever reason, this is the same reason that should be reported by the public method.

comment:8 Changed 10 years ago by rbeezer

  • Description modified (diff)

Reworked with a cleaner separation. Error-checking and tests are in the underscore method, making the regular call much shorter an I think the two following routines will work better also.

comment:9 Changed 10 years ago by novoselt

Apply only trac_12966-indefinite-factorization-v2.patch

comment:10 Changed 10 years ago by novoselt

  • Status changed from needs_review to positive_review

comment:11 Changed 10 years ago by novoselt

By the way Rob - "{0} and {1}".format(a ,b) is the same as "{} and {}".format(a, b), so you don't have to keep track of numbers.

comment:12 Changed 10 years ago by jdemeyer

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