#12280: Incorrect saturation of integer matrix
------------------------------+---------------------------------------------
Reporter: vbraun | Owner: jason, was
Type: defect | Status: needs_review
Priority: critical | Milestone: sage-5.0
Component: linear algebra | Keywords: hnf echelon_form
Work_issues: | Upstream: None of the above - read trac
for reasoning.
Reviewer: | Author: Volker Braun
Merged: | Dependencies:
------------------------------+---------------------------------------------
Description changed by vbraun:
Old description:
> 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 bug comes from `algorithm='padic'`, using Pari gives the correct
> result::
> {{{
> sage: matrix(ZZ,M)._right_kernel_matrix(algorithm='padic') # bad
> ('computed-iml-int', 76 x 76 dense matrix over Integer Ring)
> sage: matrix(ZZ,M)._right_kernel_matrix(algorithm='pari') # good
> ('computed-pari-int', 70 x 76 dense matrix over Integer Ring)
> }}}
> Conclusion: this seems to be an IML bug with threshold matrix size 76.
>
> Note that Pari is actually faster than IML for this particular matrix:
> {{{
> sage: timeit("matrix(ZZ,M)._right_kernel_matrix(algorithm='padic')")
> 5 loops, best of 3: 495 ms per loop
> sage: timeit("matrix(ZZ,M)._right_kernel_matrix(algorithm='pari')")
> 25 loops, best of 3: 30.9 ms per loop
> }}}
New description:
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.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12280#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
