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:

Status badges

Description (last modified by vbraun)

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)

trac_12280_padic_hnf_without_zero_rows.patch (7.9 KB) - added by vbraun 10 years ago.
Updated patch

Download all attachments as: .zip

Change History (12)

comment:1 Changed 10 years ago by vbraun

I built a new iml-1.0.3 spkg but it does not fix the issue.

comment:2 Changed 10 years ago by vbraun

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

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

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

  • Authors set to Volker Braun
  • 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 vbraun

  • Description modified (diff)

comment:7 Changed 10 years ago by was

NOTE: I will give this a positive review once the test suite runs and the four run-on sentences are fixed.

Changed 10 years ago by vbraun

Updated patch

comment:8 Changed 10 years ago by vbraun

The updated patch fixes the (really short) run-on sentences.

comment:9 Changed 10 years ago by was

  • Status changed from needs_review to positive_review

comment:10 Changed 10 years ago by jdemeyer

  • Reviewers set to William Stein

comment:11 Changed 10 years ago by jdemeyer

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