#12280: Incorrect kernel of integer matrix (IML bug?)
------------------------------+---------------------------------------------
Reporter: vbraun | Owner: jason, was
Type: defect | Status: new
Priority: major | Milestone: sage-4.8
Component: linear algebra | Keywords: IML kernel 76
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
------------------------------+---------------------------------------------
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
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12280>
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.
