#10625: inverse_mod for integer ring won't take an ideal as argument
-----------------------+----------------------------------------------------
Reporter: rbeezer | Owner: AlexGhitza
Type: defect | Status: new
Priority: major | Milestone: sage-4.6.2
Component: algebra | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------+----------------------------------------------------
Old description:
> The generic Smith Form routine fails for integer matrices, making me
> suspicious it needs some attention. The specialized version for integer
> matrices seems fine, so this is not a problem per se, just evidence
> something is amiss. Here's the evidence, obtained by shipping in a
> sparse matrix - this should soon be fixed by sending sparse matrices to
> the working dense version. So if you test this ''use something like
> 4.6.1 or earlier''.
>
> {{{
> sage: A = matrix(2,range(4), sparse=True)
> sage: A.smith_form()
> ---------------------------------------------------------------------------
> TypeError Traceback (most recent call
> last)
>
> /home/sage/sage-4.6.1.alpha2/<ipython console> in <module>()
>
> /home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
> packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.smith_form
> (sage/matrix/matrix2.c:37477)()
>
> /home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
> packages/sage/matrix/matrix2.so in sage.matrix.matrix2._smith_onestep
> (sage/matrix/matrix2.c:42366)()
>
> /home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
> packages/sage/matrix/matrix2.so in sage.matrix.matrix2._smith_onestep
> (sage/matrix/matrix2.c:42181)()
>
> /home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
> packages/sage/matrix/matrix2.so in
> sage.matrix.matrix2._generic_clear_column (sage/matrix/matrix2.c:41049)()
>
> /home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
> packages/sage/rings/integer.so in sage.rings.integer.Integer.inverse_mod
> (sage/rings/integer.c:28740)()
>
> /home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
> packages/sage/rings/integer.so in sage.rings.integer.as_Integer
> (sage/rings/integer.c:6052)()
>
> /home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
> packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__
> (sage/rings/integer.c:7312)()
>
> TypeError: unable to coerce <class 'sage.rings.ideal.Ideal_pid'> to an
> integer
> }}}
>
> On the input above, I think the failure is in
> `sage.matrix.matrix2._generic_clear_column` at the line:
>
> {{{
> c = R(a[0,0] / B).inverse_mod(R.ideal(a[k,0] / B))
> }}}
>
> which would be
>
> {{{
> ZZ(2/1).inverse_mod(ZZ.ideal(3/1))
> }}}
>
> which by itself fails in a similar fashion.
>
> Can you place an ideal inside `Integer.inverse_mod`?
New description:
The top level {{{inverse_mod}}} method for ring elements (in
{{{sage.structure.element.RingElement}}}) mandates that {{{inverse_mod}}}
should always take an ideal of the ring as its argument. The integer ring
doesn't implement this correctly:
{{{
sage: ZZ(2).inverse_mod(ZZ.ideal(3))
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/storage/masiao/sage-4.6.2.alpha0/devel/sage-reviewing/sage/rings/<ipython
console> in <module>()
/usr/local/sage/sage-4.6.1/local/lib/python2.6/site-
packages/sage/rings/integer.so in sage.rings.integer.Integer.inverse_mod
(sage/rings/integer.c:28740)()
5161 cdef Integer ans = <Integer>PY_NEW(Integer)
5162 if mpz_cmp_ui(m.value, 1) == 0:
-> 5163 return zero
5164 sig_on()
5165 r = mpz_invert(ans.value, self.value, m.value)
/usr/local/sage/sage-4.6.1/local/lib/python2.6/site-
packages/sage/rings/integer.so in sage.rings.integer.as_Integer
(sage/rings/integer.c:6052)()
365 return <Integer>x
366 else:
--> 367 return Integer(x)
368
369 cdef class IntegerWrapper(Integer):
/usr/local/sage/sage-4.6.1/local/lib/python2.6/site-
packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__
(sage/rings/integer.c:7312)()
678 pass
679
--> 680 raise TypeError, "unable to coerce %s to an
integer" % type(x)
681
682 def __reduce__(self):
TypeError: unable to coerce <class 'sage.rings.ideal.Ideal_pid'> to an
integer
}}}
This causes issues with the generic Smith form implementation applied to
integer matrices. Here's the evidence, obtained by shipping in a sparse
matrix - this should soon be fixed by sending sparse matrices to the
working dense version. So if you test this ''use something like 4.6.1 or
earlier''.
{{{
sage: A = matrix(2,range(4), sparse=True)
sage: A.smith_form()
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/home/sage/sage-4.6.1.alpha2/<ipython console> in <module>()
/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.smith_form
(sage/matrix/matrix2.c:37477)()
/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
packages/sage/matrix/matrix2.so in sage.matrix.matrix2._smith_onestep
(sage/matrix/matrix2.c:42366)()
/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
packages/sage/matrix/matrix2.so in sage.matrix.matrix2._smith_onestep
(sage/matrix/matrix2.c:42181)()
/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
packages/sage/matrix/matrix2.so in
sage.matrix.matrix2._generic_clear_column (sage/matrix/matrix2.c:41049)()
/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
packages/sage/rings/integer.so in sage.rings.integer.Integer.inverse_mod
(sage/rings/integer.c:28740)()
/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
packages/sage/rings/integer.so in sage.rings.integer.as_Integer
(sage/rings/integer.c:6052)()
/home/sage/sage-4.6.1.alpha2/local/lib/python2.6/site-
packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__
(sage/rings/integer.c:7312)()
TypeError: unable to coerce <class 'sage.rings.ideal.Ideal_pid'> to an
integer
}}}
--
Comment(by davidloeffler):
I don't mean to seem hostile, but: I wrote the generic Smith and Hermite
form code, and I used no assumptions on the methods of the ring elements
other than those mandated by the docstrings of the top-level
{{{sage.structure.element.RingElement}}} class. The problem is that the
Integer class doesn't play by the rules (because it's so routine to
confuse an ideal of ZZ with its non-negative generator).
So the solution is not to change the Smith form code, but to add a couple
of lines to {{{Integer.inverse_mod}}} to make it consistent with the
general ring element template.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10625#comment:1>
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.
