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: |
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)
Change History (23)
comment:1 Changed 12 years ago by
- Status changed from new to needs_review
Changed 12 years ago by
comment:2 Changed 12 years ago by
Corrected a typo in documentation
comment:3 Changed 12 years ago by
comment:4 Changed 12 years ago by
- 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: ↓ 6 Changed 12 years ago by
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
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) 4So 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: ↓ 8 Changed 12 years ago by
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: ↓ 9 Changed 12 years ago by
comment:9 in reply to: ↑ 8 Changed 12 years ago by
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
comment:10 Changed 12 years ago by
- 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
- 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
comment:12 Changed 12 years ago by
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
- Status changed from needs_work to needs_review
comment:14 Changed 12 years ago by
- 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
- 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
- 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
- Milestone changed from sage-4.6.1 to sage-4.6.2
comment:18 Changed 12 years ago by
- Reviewers changed from John Cremona, Aly Deines to John Cremona, Alyson Deines
comment:19 Changed 12 years ago by
- Reviewers changed from John Cremona, Alyson Deines to John Cremona, Aly Deines
comment:20 Changed 12 years ago by
- Merged in set to sage-4.6.2.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
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.