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: |
Description (last modified by )
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:
Attachments (3)
Change History (15)
Changed 10 years ago by
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
- 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
- Keywords sd40.5 added
Changed 10 years ago by
comment:5 follow-up: ↓ 6 Changed 10 years ago by
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 fromd
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
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 fromd
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
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.
Changed 10 years ago by
comment:8 Changed 10 years ago by
- 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
Apply only trac_12966-indefinite-factorization-v2.patch
comment:10 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:11 Changed 10 years ago by
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
- Merged in set to sage-5.1.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
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.