Opened 13 years ago
Closed 5 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 13 years ago by
comment:1 Changed 13 years ago by
- Milestone set to sage-2.10.2
comment:2 Changed 13 years ago by
- Component changed from algebraic geometry to commutative algebra
- Owner changed from was to malb
comment:3 Changed 13 years ago by
- Cc ncalexan added
- Summary changed from [with patch] implementation mpoly factoring with coefficients in ZZ to [with patch, with cautiously optimistic review] implementation mpoly factoring with coefficients in ZZ
comment:4 Changed 13 years ago by
- Summary changed from [with patch, with cautiously optimistic review] implementation mpoly factoring with coefficients in ZZ to [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 13 years ago by
- Summary changed from [with patch, negative review] implementation mpoly factoring with coefficients in ZZ to [with patch, accepted pending addition of doctests] implementation mpoly factoring with coefficients in ZZ
comment:6 Changed 13 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 13 years ago by
- Milestone changed from sage-2.10.3 to 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 13 years ago by
- Owner changed from malb to jbmohler
comment:9 Changed 13 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 13 years ago by
- Summary changed from [with patch, accepted pending addition of doctests] implementation mpoly factoring with coefficients in ZZ to [with patch, needs work] implementation mpoly factoring with coefficients in ZZ
comment:11 Changed 12 years ago by
- Keywords editor_wstein added
- Summary changed from [with patch, needs work] implementation mpoly factoring with coefficients in ZZ to [with patch, under review by burcin before 6/27] implementation mpoly factoring with coefficients in ZZ
comment:12 Changed 12 years ago by
- Summary changed from [with patch, under review by burcin before 6/27] implementation mpoly factoring with coefficients in ZZ to [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 12 years ago by
- Type changed from defect to enhancement
comment:14 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:15 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:16 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:17 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:19 Changed 6 years ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Reviewers set to Jeroen Demeyer
- Status changed from needs_work to positive_review
comment:20 Changed 5 years ago by
- Resolution set to fixed
- Status changed from positive_review to 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?