Opened 10 years ago
Closed 9 years ago
#13770 closed defect (fixed)
bug in multivariate factorization over prime fields
Reported by: | Paul Zimmermann | Owned by: | Martin Albrecht |
---|---|---|---|
Priority: | critical | Milestone: | sage-5.12 |
Component: | commutative algebra | Keywords: | sd53, singular, polynomial, factorization |
Cc: | Martin Albrecht, Simon King, Alexander Dreyer | Merged in: | sage-5.12.rc0 |
Authors: | Paul Zimmermann, Jeroen Demeyer | Reviewers: | Jean-Pierre Flori |
Report Upstream: | Fixed upstream, but not in a stable release. | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
after #11829, #11838, #12918, #12928, here is another bug in multivariate factorization over prime fields:
---------------------------------------------------------------------- | Sage Version 5.4.1, Release Date: 2012-11-15 | | Type "notebook()" for the browser-based notebook interface. | | Type "help()" for help. | ---------------------------------------------------------------------- sage: U.<y,t> = GF(2)[] sage: f y*t^8 + y^5*t^2 + y*t^6 + t^7 + y^6 + y^5*t + y^2*t^4 + y^2*t^2 + y^2*t + t^3 + y^2 + t^2 sage: f.factor() y*t^8 + y^5*t^2 + y*t^6 + t^7 + y^6 + y^5*t + y^2*t^4 + y^2*t^2 + y^2*t + t^3 + y^2 + t^2 sage: f % (t^2+t+y+1) 0
When will Sage be usable for this kind of computation?
spkg: http://boxen.math.washington.edu/home/jdemeyer/spkg/singular-3-1-5.p9.spkg (spkg diff)
apply trac_13770.patch
See also upstream https://github.com/Singular/Sources/pull/215
Attachments (2)
Change History (31)
comment:1 follow-up: 5 Changed 10 years ago by
Cc: | Simon King added |
---|
comment:2 Changed 10 years ago by
Paul,
to be fair #13672 isn't a bug in Singular but an issue with Pari and how we use it. Also, I am not sure there is a component we could use besides Singular for factoring. In any case, I've forwarded your bug report.
comment:3 Changed 10 years ago by
Report Upstream: | N/A → Reported upstream. No feedback yet. |
---|
comment:4 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:5 Changed 10 years ago by
Replying to zimmerma:
maybe one should consider replacing Singular by another more reliable component?
If there were any (for multivariate polynomials etc.), we would immediately use it in Singular. BTW: when reported upstream, the response time is quite good, I think.
comment:6 Changed 10 years ago by
Cc: | Alexander Dreyer added |
---|
comment:7 Changed 10 years ago by
Report Upstream: | Reported upstream. No feedback yet. → Fixed upstream, but not in a stable release. |
---|
from Martin Lee:
I have just committed a fix for this under 15453.
comment:8 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:9 Changed 9 years ago by
Martin Lee tells me the bug is fixed by this commit: https://github.com/Singular/Sources/pull/215
Also it is fixed in Singular 3-1-6. Any plan to upgrade the Singular version?
Martin also tells me Singular 3-1-7 is planned within the next month.
Paul
Changed 9 years ago by
Attachment: | trac_13770.patch added |
---|
comment:10 follow-up: 11 Changed 9 years ago by
Authors: | → Paul Zimmermann |
---|---|
Status: | new → needs_review |
on http://www.loria.fr/~zimmerma/singular-3-1-5.p8.spkg I've put an updated Singular spkg which includes the first patch of https://github.com/Singular/Sources/pull/215. This seems to be enough to solve this bug.
The attached patch adds a non-regression test.
Paul
comment:11 Changed 9 years ago by
Replying to zimmerma:
on http://www.loria.fr/~zimmerma/singular-3-1-5.p8.spkg I've put an updated Singular spkg which includes the first patch of https://github.com/Singular/Sources/pull/215.
Wouldn't it be safer to include all four commits? Did you check whether this solves #14658?
comment:12 Changed 9 years ago by
Description: | modified (diff) |
---|
comment:13 Changed 9 years ago by
Description: | modified (diff) |
---|
comment:14 Changed 9 years ago by
Jeroen,
Wouldn't it be safer to include all four commits?
indeed (maybe only the first three, since the last one only adds tests). But I didn't know how to extract the diff, thus I edited the Singular source file manually, it took then several hours on my laptop to recompile the spkg and rebuild Sage, thus I was quite happy it worked (currently running sage -t --long).
Did you check whether this solves #14658?
unfortunately not. The first example of #14658 does no longer produce an error (same with vanilla 5.11 btw) but the factorization is incomplete:
sage: R.<x1,x2,x3> = QQ['x1,x2,x3'] sage: f = (x1+x2+x3)*(2*x1-x2+x3+2)*(4*x1+x2+x3+2)*(8*x1-x2+x3+4) sage: f.factor() (x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16)
The other example still breaks with Floating point exception
.
Paul
comment:16 Changed 9 years ago by
Authors: | Paul Zimmermann → Paul ZImmermann, Jeroen Demeyer |
---|---|
Status: | needs_review → needs_work |
When updating a spkg, you should add a Changelog entry in SPKG.txt
. Also, changes should be committed to the Mercurial repo (hg add patches/singular_13770.patch
and hg commit
).
I will make these changes and try to use the 3 commits from the upstream pull request.
comment:17 Changed 9 years ago by
To download patches from github, see http://stackoverflow.com/questions/6188591/download-github-pull-request-as-unified-diff (I agree it is hard to find out)
comment:19 Changed 9 years ago by
thank you Jeroen for the pointers. I thus let you continue on this ticket.
Paul
comment:20 Changed 9 years ago by
Authors: | Paul ZImmermann, Jeroen Demeyer → Paul Zimmermann, Jeroen Demeyer |
---|
comment:21 Changed 9 years ago by
Authors: | Paul Zimmermann, Jeroen Demeyer → Paul ZImmermann, Jeroen Demeyer |
---|
just answering to my own question:
Also it is fixed in Singular 3-1-6. Any plan to upgrade the Singular version?
this is planned in #14333
Paul
comment:22 Changed 9 years ago by
Authors: | Paul ZImmermann, Jeroen Demeyer → Paul Zimmermann, Jeroen Demeyer |
---|
comment:23 Changed 9 years ago by
Description: | modified (diff) |
---|
Changed 9 years ago by
Attachment: | singular-3-1-5.p9.diff added |
---|
comment:24 Changed 9 years ago by
Description: | modified (diff) |
---|
comment:25 Changed 9 years ago by
Status: | needs_work → needs_review |
---|
New spkg is up, but I still need to test it properly myself.
comment:26 Changed 9 years ago by
#14658 is still not fixed:
sage: R.<x1,x2,x3> = QQ['x1,x2,x3'] sage: f = (x1+x2+x3)*(2*x1-x2+x3+2)*(4*x1+x2+x3+2)*(8*x1-x2+x3+4) sage: f.factor() (x1 + x2 + x3) * (2*x1 - x2 + x3 + 2) * (32*x1^2 + 4*x1*x2 - x2^2 + 12*x1*x3 + x3^2 + 32*x1 + 2*x2 + 6*x3 + 8)
Note that we do not even get deterministic answers:
sage: f.factor() (x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16) sage: f.factor() (x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16) sage: f.factor() (x1 + x2 + x3) * (2*x1 - x2 + x3 + 2) * (32*x1^2 + 4*x1*x2 - x2^2 + 12*x1*x3 + x3^2 + 32*x1 + 2*x2 + 6*x3 + 8) sage: f.factor() (x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16) sage: f.factor() (x1 + x2 + x3) * (8*x1 - x2 + x3 + 4) * (8*x1^2 - 2*x1*x2 - x2^2 + 6*x1*x3 + x3^2 + 12*x1 + 4*x3 + 4) sage: f.factor() (x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16) sage: f.factor() (x1 + x2 + x3) * (8*x1 - x2 + x3 + 4) * (8*x1^2 - 2*x1*x2 - x2^2 + 6*x1*x3 + x3^2 + 12*x1 + 4*x3 + 4) sage: f.factor() (x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16) sage: f.factor() --------------------------------------------------------------------------- RuntimeError Traceback (most recent call last) <ipython-input-25-429743410e57> in <module>() ----> 1 f.factor() /localdisk/tmp/sage-5.11/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_libsingular.so in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.factor (sage/rings/polynomial/multi_polynomial_libsingular.cpp:26013)() RuntimeError: Segmentation fault
comment:28 Changed 9 years ago by
Keywords: | sd53 singular polynomial factorization added |
---|---|
Reviewers: | → Jean-Pierre Flori |
Status: | needs_review → positive_review |
Looks good. Lets get this in even though updating to Singular 3-1-6 or even 3-1-7 should supersede it, but needs more serious work. (Moreover singular website is down right now.)
comment:29 Changed 9 years ago by
Merged in: | → sage-5.12.rc0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
maybe one should consider replacing Singular by another more reliable component?
Paul