Opened 15 years ago
Closed 7 years ago
#2179 closed enhancement (fixed)
[with patch, needs work] implementation mpoly factoring with coefficients in ZZ
Reported by: | jbmohler | Owned by: | jbmohler |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | commutative algebra | Keywords: | editor_wstein |
Cc: | ncalexan | Merged in: | |
Authors: | Reviewers: | Jeroen Demeyer | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Here's a pure python implementation of an algorithm to factor polynomials over ZZ using kronecker's trick (specializing a variable to a large prime reduces you to a poly of fewer variables). Note that this also fills in an implementation of factoring over ZZ[x,y] --- we don't have any implementation at all for this currently. It's also faster than singular (over QQ) for some cases.
Here's an example with my favorite trouble-maker for singular.
this patch:
sage: R.<p10,g0,g1,g2,g3,g4,X1,X2>=ZZ[] sage: t=-p10^170*X1^10*X2^10+p10^130*X1^10*X2^5+p10^130*X1^5*X2^10-p10^90*X1^5*X2^5+p10^80*X1^5*X2^5-p10^40*X1^5-p10^40*X2^5+1 sage: time t.factor() CPU times: user 0.11 s, sys: 0.00 s, total: 0.12 s Wall time: 0.12 (-1) * (p10^8*X2 - 1) * (p10^8*X1 - 1) * (p10^18*X1*X2 - 1) * (p10^32*X2^4 + p10^24*X2^3 + p10^16*X2^2 + p10^8*X2 + 1) * (p10^32*X1^4 + p10^24*X1^3 + p10^16*X1^2 + p10^8*X1 + 1) * (p10^72*X1^4*X2^4 + p10^54*X1^3*X2^3 + p10^36*X1^2*X2^2 + p10^18*X1*X2 + 1)
singular:
sage: R.<p10,g0,g1,g2,g3,g4,X1,X2>=QQ[] sage: t=-p10^170*X1^10*X2^10+p10^130*X1^10*X2^5+p10^130*X1^5*X2^10-p10^90*X1^5*X2^5+p10^80*X1^5*X2^5-p10^40*X1^5-p10^40*X2^5+1 sage: time t.factor() CPU times: <longer than I wanted to wait>
Attachments (1)
Change History (21)
Changed 15 years ago by
Attachment: | mpoly-factor.patch added |
---|
comment:1 Changed 15 years ago by
Milestone: | → sage-2.10.2 |
---|
comment:2 Changed 15 years ago by
Component: | algebraic geometry → commutative algebra |
---|---|
Owner: | changed from William Stein to Martin Albrecht |
comment:3 Changed 15 years ago by
Cc: | ncalexan added |
---|---|
Summary: | [with patch] implementation mpoly factoring with coefficients in ZZ → [with patch, with cautiously optimistic review] implementation mpoly factoring with coefficients in ZZ |
comment:4 Changed 15 years ago by
Summary: | [with patch, with cautiously optimistic review] implementation mpoly factoring with coefficients in ZZ → [with patch, negative review] implementation mpoly factoring with coefficients in ZZ |
---|
REVIEW:
This absolutely should not be applied for the simple reason that the file sage/rings/polynomial/multi_polynomial_factor.py
introduces 7 new functions that have 0 docstrings and 0 doctests, and essentially 0 documentation. My understanding, which I want to push very hard, is that no new code should go into Sage that reduces the overall doctest coverage score.
Joel -- can you add doctests and docstrings for every single function multi_polynomial_factor.py
? I do that with *all* new code I write for Sage.
comment:5 Changed 15 years ago by
Summary: | [with patch, negative review] implementation mpoly factoring with coefficients in ZZ → [with patch, accepted pending addition of doctests] implementation mpoly factoring with coefficients in ZZ |
---|
comment:6 Changed 15 years ago by
I'm reviewing my own code today. Expect a new patch to be submitted as of later today. I just thought I'd mention that here in case someone was looking at this code today.
comment:7 Changed 15 years ago by
Milestone: | sage-2.10.3 → sage-3.0 |
---|
I'm retracting this for the moment. As expected, once I started looking at this code I found so many ways to improve it and totally got sucked in again and want to make it better.
comment:8 Changed 15 years ago by
Owner: | changed from Martin Albrecht to jbmohler |
---|
comment:9 Changed 14 years ago by
Here is what Magma does, for the record:
And for GCD:
http://magma.maths.usyd.edu.au/magma/htmlhelp/text314.htm#1994
comment:10 Changed 14 years ago by
Summary: | [with patch, accepted pending addition of doctests] implementation mpoly factoring with coefficients in ZZ → [with patch, needs work] implementation mpoly factoring with coefficients in ZZ |
---|
comment:11 Changed 14 years ago by
Keywords: | editor_wstein added |
---|---|
Summary: | [with patch, needs work] implementation mpoly factoring with coefficients in ZZ → [with patch, under review by burcin before 6/27] implementation mpoly factoring with coefficients in ZZ |
comment:12 Changed 14 years ago by
Summary: | [with patch, under review by burcin before 6/27] implementation mpoly factoring with coefficients in ZZ → [with patch, needs work] implementation mpoly factoring with coefficients in ZZ |
---|
Joel says he has an improved patch with various additional tricks to filter easy factors. I will wait for an updated patch to review this.
comment:13 Changed 14 years ago by
Type: | defect → enhancement |
---|
comment:14 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:15 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:16 Changed 8 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:17 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:19 Changed 7 years ago by
Milestone: | sage-6.4 → sage-duplicate/invalid/wontfix |
---|---|
Reviewers: | → Jeroen Demeyer |
Status: | needs_work → positive_review |
comment:20 Changed 7 years ago by
Resolution: | → fixed |
---|---|
Status: | positive_review → closed |
I am no expert on factoring algorithms, but this does seem to fill a needed hole, is reasonably implemented, and has some rudimentary doctests.
I say apply.
Isn't this whole area going to be addressed soon anyway, so that this code will likely be reviewed and enhanced shortly?