Opened 12 years ago

Closed 12 years ago

#9063 closed defect (fixed)

wrong type for denominator

Reported by: cjh Owned by: AlexGhitza
Priority: major Milestone: sage-4.6.2
Component: algebra Keywords:
Cc: Merged in: sage-4.6.2.alpha1
Authors: Luis Felipe Tabera Alonso Reviewers: John Cremona, Aly Deines
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

If you create a polynomial in one variable over a finite field and ask for the denominator, then the answer you get has the wrong type when the polynomial is the zero polynomial. Here's an example:

sage: R.<t> = GF(5)['t']
sage: x = R(0)
sage: type(x.denominator())
<type 'int'>

Attachments (3)

trac_9063.patch (3.2 KB) - added by lftabera 12 years ago.
weak-popof-form.patch (3.6 KB) - added by lftabera 12 years ago.
weak-popof-form.2.patch (4.0 KB) - added by lftabera 12 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 12 years ago by lftabera

  • Status changed from new to needs_review

If the element of the ring is zero or the base_ring does not have a denominator function, the code returned the "wrong 1", either int 1 or polynomial 1. The patch correct this.

Changed 12 years ago by lftabera

comment:2 Changed 12 years ago by lftabera

Corrected a typo in documentation

comment:3 Changed 12 years ago by lftabera

  • Authors set to Luis Felipe Tabera Alonso

comment:4 Changed 12 years ago by cremona

  • Reviewers set to John Cremona
  • Status changed from needs_review to needs_work

This looks good to me. It applied ok to 4.5.3.alpha1, and all (long) tests pass, except for one:

sage -t -long "sage/matrix/matrix2.pyx"                     
**********************************************************************
File "/storage/jec/sage-4.5.3.alpha1/devel/sage-tests/sage/matrix/matrix2.pyx", line 4665:
    sage: M.weak_popov_form()
Exception raised:
    Traceback (most recent call last):
      File "/home/jec/sage-current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/jec/sage-current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/jec/sage-current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_68[7]>", line 1, in <module>
        M.weak_popov_form()###line 4665:
    sage: M.weak_popov_form()
      File "matrix2.pyx", line 4748, in sage.matrix.matrix2.Matrix.weak_popov_form (sage/matrix/matrix2.c:26417)
        ::
      File "/home/jec/sage-current/local/lib/python/site-packages/sage/matrix/matrix_misc.py", line 90, in weak_popov_form
        den = R(lcm([a.denominator() for a in M.list()]))
      File "/home/jec/sage-current/local/lib/python/site-packages/sage/rings/arith.py", line 1527, in lcm
        return __LCM_sequence(seq)
      File "/home/jec/sage-current/local/lib/python/site-packages/sage/rings/arith.py", line 1583, in __LCM_sequence
        g = vi.lcm(g)
      File "element.pyx", line 306, in sage.structure.element.Element.__getattr__ (sage/structure/element.c:2632)
        return getattr_from_other_class(self, self.parent().category().element_class, name)
      File "parent.pyx", line 268, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:2835)
        raise_attribute_error(self, name)
      File "parent.pyx", line 170, in sage.structure.parent.raise_attribute_error (sage/structure/parent.c:2602)
        raise AttributeError, "'%s.%s' object has no attribute '%s'"%(cls.__module__, cls.__name__, name)
    AttributeError: 'sage.rings.finite_rings.integer_mod.IntegerMod_int' object has no attribute 'lcm'
**********************************************************************
1 items had failures:

The problem is in the function weak_popov_form() in sage/rings/matrix/matrix_misc.py (which was only merged into Sage receontly -- and I was, by chance, its reviewer). There one has matrices of polynomials over fields and the code tries to clear denominators, by forming the LCM of the denominators; and that now fails when those denominators are all equal to 1 in a finite field!

Rather than mess with the weakpopov form code, this could be solved if there was an lcm function for finite field elements which always returned 1 (except lcm(0,0)=0, perhaps).

comment:5 follow-up: Changed 12 years ago by lftabera

Well,

The issue of adding a lcm function for finite fields has some problems associated:

  • Except is degenerate cases, all elements are units, so the lcm being 1 is not nonsense.
  • The problem is that currently, sage already does some lcm for finite fields if the elements can be coerced to ZZ.
sage: m = GF(5)
sage: a= m(4)
sage: lcm(a,a)
4

So this approach will add a backwards incompatibility at least.

comment:6 in reply to: ↑ 5 Changed 12 years ago by cremona

Replying to lftabera:

Well,

The issue of adding a lcm function for finite fields has some problems associated:

  • Except is degenerate cases, all elements are units, so the lcm being 1 is not nonsense.
  • The problem is that currently, sage already does some lcm for finite fields if the elements can be coerced to ZZ.
sage: m = GF(5)
sage: a= m(4)
sage: lcm(a,a)
4

So this approach will add a backwards incompatibility at least.

Well spotted! I think that this current behavour is a bug:

sage: a = GF(5)(4)
sage: type(a)
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
sage: lcm(a,a)
4
sage: type(lcm(a,a))
<type 'sage.rings.integer.Integer'>

since it makes no mathematical sense at all. It's the same for gcd:

sage: gcd(a,a)
4
sage: type(gcd(a,a))
<type 'sage.rings.integer.Integer'>

Both of these would not happen if finite field elements have gcd and lcm methods, and in my opinion that would be better.

Someone should try to implement this and do a full test to see if any existing code (tests) is broken. I hope not -- I cannot imagine anyone relying on this rather crazy behaviour.

comment:7 follow-up: Changed 12 years ago by lftabera

I have added a new bug dealing with the issue of lcm. So this bug now depends on #9819

comment:8 in reply to: ↑ 7 ; follow-up: Changed 12 years ago by cremona

Replying to lftabera:

I have added a new bug dealing with the issue of lcm. So this bug now depends on #9819

I hope you do not mean exactly what you wrote!

comment:9 in reply to: ↑ 8 Changed 12 years ago by lftabera

Replying to cremona:

Replying to lftabera:

I have added a new bug dealing with the issue of lcm. So this bug now depends on #9819

I hope you do not mean exactly what you wrote!

What do you exactly mean? I think this is the correct wayy to go. The problem may be solved by a workaround on weak_popov_form, but surely will appear on other instances of fields or other methods that may be added in the future.

Changed 12 years ago by lftabera

comment:10 Changed 12 years ago by lftabera

  • Status changed from needs_work to needs_review

I have attached another patch that solves the problem in weak_popov_form.

I follow the python mantra of 'explicit better than implicit'. The algorithm expects as entries a matrix with rational functions as entries.

If the entries are polynomials, then the algorithm may fail because the denominators will be elements in a field and currently sage does not consider this case for all fields.

Now, the algorithm first transforms the input matrix to a matrix with rational functions as entries which is the domain the algorithm is expected to work. The denominators will then be polynomials and the algorithm will work as expected.

I have added a doctest to check that the output is the same in the polynomial and rational function case.

As a side effect, I correct a typo in the documentation of weak_popov_form. The documentation asserts that the output is (W, N, t) where W and N are matrices of rational functions. In fact, N is a matrix of polynomials.

Both patches can be applied in any order. With this patch bug #9819 does not apply.

comment:11 Changed 12 years ago by burcin

  • Status changed from needs_review to needs_work

AFAICT, the weak_popov_form function clears the denominators to work over the polynomial ring instead of the fraction field. When a matrix over the polynomial ring is given, it seems inefficient to first coerce all entries to the fraction field, then find the denominator 1 and go back to the polynomials we were given.

Can't we just avoid clearing the denominators if R (in the first line) is a field (and not call lcm())?

Changed 12 years ago by lftabera

comment:12 Changed 12 years ago by lftabera

I have added a new patch to weak_popov_form so it does not perform any cleaning of denominadors when the matrix has polynomial entries.

Apply:

trac_9063.patch

weak-popof-form.2.patch

In any order

comment:13 Changed 12 years ago by lftabera

  • Status changed from needs_work to needs_review

comment:14 Changed 12 years ago by gagansekhon

  • Status changed from needs_review to needs_work

failed on coverage for both files

./sage -coverage sage/rings/polynomial/multi_polynomial.pyx


sage/rings/polynomial/multi_polynomial.pyx ERROR: Please add a TestSuite(s).run() doctest. SCORE sage/rings/polynomial/multi_polynomial.pyx: 89% (33 of 37)

Missing documentation:

  • is_MPolynomial(x):
  • _polynomial_(self, R):
  • hash(self):

Missing doctests:

  • truncate(self, var, n):

./sage -coverage sage/matrix/matrix2.pyx ---------------------------------------------------------------------- sage/matrix/matrix2.pyx SCORE sage/matrix/matrix2.pyx: 92% (104 of 112)

Missing documentation:

  • _row_ambient_module(self, base_ring=None):
  • _column_ambient_module(self):
  • _decomposition_using_kernels(self, is_diagonalizable=False, dual=False):

Missing doctests:

  • _decomposition_spin_generic(self, is_diagonalizable=False):
  • eigenspaces(self, var='a', even_if_inexact=None):
  • _echelon_classical(self):
  • _cholesky_decomposition_(self):
  • cmp_pivots(x,y):

comment:15 Changed 12 years ago by gagansekhon

  • Status changed from needs_work to needs_review

Sorry, I was following developers guide, which stated if coverage is less than 100% than it needs work. However, given the functions that you changed are not the ones where coverage failed, I put it back to needs_review. I will be running other test now

comment:16 Changed 12 years ago by aly.deines

  • Reviewers changed from John Cremona to John Cremona, Aly Deines
  • Status changed from needs_review to positive_review

Looks good to me.

comment:17 Changed 12 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:18 Changed 12 years ago by jdemeyer

  • Reviewers changed from John Cremona, Aly Deines to John Cremona, Alyson Deines

comment:19 Changed 12 years ago by jdemeyer

  • Reviewers changed from John Cremona, Alyson Deines to John Cremona, Aly Deines

comment:20 Changed 12 years ago by jdemeyer

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