Opened 10 years ago
Closed 10 years ago
#12280 closed defect (fixed)
Incorrect saturation of integer matrix
Reported by: | vbraun | Owned by: | jason, was |
---|---|---|---|
Priority: | critical | Milestone: | sage-5.0 |
Component: | linear algebra | Keywords: | hnf echelon_form |
Cc: | was, cremona, nbruin | Merged in: | sage-5.0.beta6 |
Authors: | Volker Braun | Reviewers: | William Stein |
Report Upstream: | None of the above - read trac for reasoning. | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This bug happens with matrices with 76 columns (but not 75) whose entries are random integers -1 or 1. The actual entries matter, but the following random choice is quite reliable at triggering it:
sage: M = matrix(ZZ, 10,76,lambda i,j: randrange(-1,3,2)) sage: M.right_kernel().basis()[-1].is_zero() True
Note that a basis vector of the null space should never be zero, so the correct output is always False
.
For reference, here is a 6 x 76 matrix that triggers the bug:
M = matrix(ZZ, [(1, -1, -1, -1, 1, 1), (-1, -1, 1, -1, 1, -1), (1, 1, 1, -1, 1, -1), (-1, 1, 1, 1, -1, -1), (1, -1, 1, -1, -1, -1), (1, -1, 1, 1, 1, 1), (-1, -1, 1, -1, 1, -1), (-1, 1, -1, -1, -1, -1), (1, -1, 1, 1, -1, -1), (-1, 1, -1, 1, 1, 1), (1, -1, -1, -1, -1, 1), (1, -1, 1, 1, -1, -1), (-1, -1, -1, -1, 1, -1), (1, 1, -1, 1, -1, 1), (-1, 1, -1, 1, 1, -1), (1, -1, 1, 1, 1, 1), (-1, -1, 1, 1, -1, -1), (1, -1, 1, 1, -1, -1), (1, -1, 1, 1, -1, 1), (-1, -1, 1, -1, -1, 1), (1, -1, -1, 1, -1, -1), (1, -1, 1, 1, 1, -1), (-1, 1, 1, -1, 1, -1), (1, -1, -1, 1, -1, -1), (-1, -1, 1, -1, -1, -1), (1, 1, -1, 1, 1, -1), (1, 1, -1, 1, 1, -1), (1, 1, 1, -1, 1, -1), (-1, 1, -1, -1, 1, -1), (-1, -1, -1, 1, -1, 1), (1, -1, -1, 1, 1, -1), (-1, 1, 1, -1, 1, 1), (-1, 1, 1, 1, 1, -1), (1, -1, -1, 1, -1, -1), (-1, 1, 1, -1, 1, -1), (-1, 1, -1, -1, 1, 1), (-1, 1, -1, -1, 1, -1), (-1, 1, -1, 1, -1, -1), (-1, -1, 1, -1, -1, -1), (-1, -1, 1, 1, -1, -1), (1, -1, -1, 1, 1, -1), (1, -1, 1, -1, -1, 1), (-1, 1, 1, -1, -1, 1), (-1, -1, -1, 1, -1, -1), (-1, 1, 1, 1, 1, 1), (-1, 1, 1, 1, -1, -1), (-1, 1, 1, 1, -1, -1), (1, -1, -1, 1, -1, 1), (1, 1, -1, -1, -1, 1), (-1, 1, -1, -1, 1, -1), (-1, -1, 1, 1, 1, 1), (-1, -1, -1, 1, 1, 1), (1, -1, 1, 1, -1, 1), (1, -1, 1, 1, 1, 1), (1, -1, 1, 1, -1, -1), (1, -1, -1, -1, -1, 1), (1, -1, -1, 1, -1, 1), (-1, 1, -1, 1, -1, -1), (1, -1, -1, 1, 1, -1), (1, -1, 1, -1, -1, 1), (-1, -1, -1, 1, -1, 1), (-1, -1, 1, -1, -1, 1), (1, 1, -1, -1, -1, -1), (1, 1, 1, 1, -1, -1), (1, 1, -1, 1, 1, -1), (-1, -1, 1, 1, -1, 1), (1, 1, 1, 1, 1, 1), (-1, 1, 1, 1, 1, 1), (1, 1, 1, -1, 1, 1), (1, 1, 1, 1, -1, 1), (1, -1, -1, 1, 1, -1), (1, -1, -1, -1, -1, -1), (1, 1, 1, -1, -1, 1), (-1, 1, -1, 1, 1, 1), (1, 1, 1, -1, -1, -1), (1, -1, 1, 1, 1, 1)] ).transpose()
The actual cause is that there is fallback to pari in algorithm='padic'
if the matrix is ill-conditioned, but we did not pass include_zero_rows=False in this case. This is fixed in the patch.
While adding doctests, I noted that pari with flag=4, include_zero_rows=False also gives an incorrect result. The patch also disables this combination, the follow-up ticket #12346 will deal with this and re-enable it once this issue is fixed upstream.
Attachments (1)
Change History (12)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
- Cc was cremona nbruin added
- Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.
comment:3 Changed 10 years ago by
- Keywords saturation added; IML kernel 76 removed
- Report Upstream changed from Not yet reported upstream; Will do shortly. to N/A
- Summary changed from Incorrect kernel of integer matrix (IML bug?) to Incorrect saturation of integer matrix
I was off-track; IML computes the correct kernel but Sage then returns its saturation. It turns out that computing the saturation introduces the extra null vectors
sage: K = M._rational_kernel_iml().transpose(); K 70 x 76 dense matrix over Integer Ring (type 'print K.str()' to see all of the entries) sage: K.saturation() 76 x 76 dense matrix over Integer Ring sage: K.saturation().row(71).is_zero() True
comment:4 Changed 10 years ago by
- Keywords hnf echelon_form added; saturation removed
75 is the cutoff where the hnf computation switches from algorithm='pari'
to
algorithm='padic'
`. The latter does not always chop off zero rows:
sage: m = matrix([(-2, 1, 9, 2, -8, 1, -3, -1, -4, -1), ... (5, -2, 0, 1, 0, 4, -1, 1, -2, 0), ... (-11, 3, 1, 0, -3, -2, -1, -11, 2, -2), ... (-1, 1, -1, -2, 1, -1, -1, -1, -1, 7), ... (-2, -1, -1, 1, 1, -2, 1, 0, 2, -4)]).stack( ... 200 * identity_matrix(ZZ, 10)) sage: matrix(ZZ,m).hermite_form(algorithm='padic', include_zero_rows=False) [ 1 0 2 0 13 5 1 166 72 69] [ 0 1 1 0 20 4 15 195 65 190] [ 0 0 4 0 24 5 23 22 51 123] [ 0 0 0 1 23 7 20 105 60 151] [ 0 0 0 0 40 4 0 80 36 68] [ 0 0 0 0 0 10 0 100 190 170] [ 0 0 0 0 0 0 25 0 100 150] [ 0 0 0 0 0 0 0 200 0 0] [ 0 0 0 0 0 0 0 0 200 0] [ 0 0 0 0 0 0 0 0 0 200] [ 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0]
comment:5 Changed 10 years ago by
- Priority changed from major to critical
- Report Upstream changed from N/A to None of the above - read trac for reasoning.
- Status changed from new to needs_review
The actual cause is that there was a fallback to pari in case of an ill-conditioned matrix (which this one turns out to be), but we did not pass include_zero_rows=False
in this case. This is fixed in the patch.
While adding doctests, I noted that pari with flag=4, include_zero_rows=False
also gives an incorrect result. The patch also disables this combination, the follow-up ticket #12346 will deal with this and re-enable it once this issue is fixed upstream.
comment:6 Changed 10 years ago by
- Description modified (diff)
comment:7 Changed 10 years ago by
NOTE: I will give this a positive review once the test suite runs and the four run-on sentences are fixed.
comment:8 Changed 10 years ago by
The updated patch fixes the (really short) run-on sentences.
comment:9 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:10 Changed 10 years ago by
- Reviewers set to William Stein
comment:11 Changed 10 years ago by
- Merged in set to sage-5.0.beta6
- Resolution set to fixed
- Status changed from positive_review to closed
I built a new iml-1.0.3 spkg but it does not fix the issue.