Opened 10 years ago
Closed 10 years ago
#10625 closed defect (fixed)
inverse_mod for integer ring won't take an ideal as argument
Reported by: | rbeezer | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | algebra | Keywords: | |
Cc: | davidloeffler | Merged in: | sage-4.6.2.alpha2 |
Authors: | David Loeffler | Reviewers: | Rob Beezer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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
Attachments (1)
Change History (6)
comment:1 Changed 10 years ago by
- Description modified (diff)
- Summary changed from Generic smith form of a matrix fails on integer matrix to inverse_mod for integer ring won't take an ideal as argument
comment:2 Changed 10 years ago by
- Status changed from new to needs_review
Here's the required 2-line patch.
comment:3 Changed 10 years ago by
Hi David,
Thanks for the explanation, and the patch (and the review on #10626). I spent several hours tracking down a number field doctest-failure to this "problem" with a sparse matrix being shipped to the generic routine. At that point, I was just puzzled by the failure of the generic code to behave properly on a simple example and did not dig any deeper. In retrospect, a post to sage-devel might have been a better course, but I knew you would know what was up. So thanks again for the explanation and the fix.
I'll work up a review of this later today.
Rob
comment:4 Changed 10 years ago by
- Reviewers set to Rob Beezer
- Status changed from needs_review to positive_review
Passes all tests on 4.6.1.alpha3, rectifies problem at #10626, and looks good. Positive review.
comment:5 Changed 10 years ago by
- Merged in set to sage-4.6.2.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
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.