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)

mpoly-factor.patch (11.5 KB) - added by jbmohler 13 years ago.

Download all attachments as: .zip

Change History (21)

Changed 13 years ago by jbmohler

comment:1 Changed 13 years ago by jbmohler

  • Milestone set to sage-2.10.2

comment:2 Changed 13 years ago by jbmohler

  • Component changed from algebraic geometry to commutative algebra
  • Owner changed from was to malb

comment:3 Changed 13 years ago by ncalexan

  • 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

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?

comment:4 Changed 13 years ago by was

  • 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 was

  • 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 jbmohler

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 jbmohler

  • 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 malb

  • Owner changed from malb to jbmohler

comment:10 Changed 13 years ago by malb

  • 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 craigcitro

  • 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 burcin

  • 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 malb

  • Type changed from defect to enhancement

comment:14 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:15 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:16 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:17 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:18 Changed 6 years ago by mmezzarobba

  • Report Upstream set to N/A

Related: #17840

comment:19 Changed 6 years ago by jdemeyer

  • 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 vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.