Opened 9 years ago

Closed 8 years ago

#10902 closed defect (fixed)

proof=False unnecessary in factor()

Reported by: zimmerma Owned by: malb
Priority: critical Milestone: sage-5.1
Component: commutative algebra Keywords: sd34
Cc: malb, SimonKing Merged in: sage-5.1.beta0
Authors: Martin Albrecht Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #10903 Stopgaps:

Description (last modified by malb)

There are currently no known counter examples where Singular would return an incorrect factorisation. It might be very very slow but does not return wrong answers as far as we know. Hence, we should drop proof=False.

Attachments (1)

trac_10902_factor.patch (13.5 KB) - added by malb 8 years ago.

Download all attachments as: .zip

Change History (33)

comment:1 follow-up: Changed 9 years ago by malb

comment:2 in reply to: ↑ 1 Changed 9 years ago by zimmerma

Dear Martin,

Replying to malb:

I reported this upstream: http://www.singular.uni-kl.de:8002/trac/ticket/320

this ticket is empty on my browser (firefox). Also, is there a workaround to factor bivariate polynomials over a prime field from within Sage, in particular over GF(2)?

Paul

comment:3 follow-up: Changed 9 years ago by malb

Paul, the Singular developers replied on that ticket and state that this bug is fixed in Singular 3-1-2. Updating to 3-1-2 is now #10903.

As for a workaround, I cannot immediately think of any. It's a pretty grim situation, but at least now there is a Singular developer working on factoring.

comment:4 in reply to: ↑ 3 Changed 9 years ago by zimmerma

Replying to malb:

Paul, the Singular developers replied on that ticket and state that this bug is fixed in Singular 3-1-2. Updating to 3-1-2 is now #10903.

As for a workaround, I cannot immediately think of any. It's a pretty grim situation, but at least now there is a Singular developer working on factoring.

thanks Martin. Once Singular is updated to 3-1-2, I will try to find examples where the factorization returned by Singular is incomplete. It would help to have concrete examples in the documentation.

Paul

comment:5 Changed 9 years ago by malb

3-1-2 should also improve this, but there are some issues that are only resolved in whatever is the next version of Singular, cf. http://www.singular.uni-kl.de:8002/trac/ticket/291#comment:4

comment:6 follow-up: Changed 9 years ago by dsm

Is this really so bad?

def check(f0, f1):
    CP = CartesianProduct(*[f0.base_ring()]*len(f0.variables()))
    for xvec in CP:
        f0_val = f0.subs(dict((v, xv) for v, xv in zip(f0.variables(), xvec)))
        f1_val = f1.subs(dict((v, xv) for v, xv in zip(f0.variables(), xvec)))
        print xvec, f0_val, f1_val, f0_val == f1_val

sage: f0 = x^5 * y^8 * (x*y^4 + y^3 + 1)
sage: f1 = x^5 * y^6 * (x*y^4 + y^3 + 1)
sage: check(f0, f1)
[0, 0] 0 0 True
[0, 1] 0 0 True
[1, 0] 0 0 True
[1, 1] 1 1 True

The factor of y^2 has no effect, so aren't the two polynomials equivalent in GF(2)? This happens pretty frequently:

sage: f0 = x**8+y**8+1
sage: f1 = f0.factor(proof=False)
sage: f1
(x + y + 1)^6
sage: f1.expand()
x^6 + x^4*y^2 + x^2*y^4 + y^6 + x^4 + y^4 + x^2 + y^2 + 1
sage: check(f0, f1.expand())
[0, 0] 1 1 True
[0, 1] 0 0 True
[1, 0] 0 0 True
[1, 1] 1 1 True

Is there a case where the two expressions aren't equivalent as functions? Or am I missing something obvious like usual?

comment:7 in reply to: ↑ 6 Changed 9 years ago by malb

Replying to dsm:

Is there a case where the two expressions aren't equivalent as functions? Or am I missing something obvious like usual?

But polynomials over GF(2) are not merely boolean functions. There's a one-to-one mapping between square-free polynomials over GF(2) and boolean functions, but polynomials are more than that. So I'd say it is very bad.

comment:8 Changed 9 years ago by zimmerma

here is another example over GF(2):

sage: R.<x,y> = GF(2)[]
sage: p=x^8 + y^8; q=x^2*y^4 + x; f=p*q
sage: lf = f.factor(proof=False)
sage: f-lf
x^10*y^4 + x^2*y^12 + x^8*y^4 + x^6*y^6 + x^4*y^8 + x^2*y^10 + x^9 + x*y^8 + x^7 + x^5*y^2 + x^3*y^4 + x*y^6

An example over GF(3):

sage: R.<x,y> = GF(3)[]
sage: p = -x*y^9 + x
sage: q = -x^8*y^2
sage: f = p*q
sage: f
x^9*y^11 - x^9*y^2
sage: f.factor(proof=False)
y^2 * (y - 1)^6 * x^6

comment:9 Changed 9 years ago by zimmerma

and an example over GF(5):

sage: R.<x,y> = GF(5)[]
sage: p=x^27*y^9 + x^32*y^3 + 2*x^20*y^10 - x^4*y^24 - 2*x^17*y
sage: q=-2*x^10*y^24 + x^9*y^24 - 2*x^3*y^30
sage: f=p*q; f-f.factor(proof=False)
-2*x^37*y^33 - 2*x^42*y^27 + x^36*y^33 - 2*x^30*y^39 + x^41*y^27 - 2*x^35*y^33 + x^30*y^34 + 2*x^29*y^34 + x^23*y^40 + 2*x^14*y^48 - x^13*y^48 + 2*x^7*y^54 + 2*x^37*y^18 + 2*x^42*y^12 - x^36*y^18 + 2*x^30*y^24 - x^41*y^12 + 2*x^35*y^18 - x^27*y^25 - 2*x^26*y^25 - x^20*y^31 - x^30*y^19 - 2*x^29*y^19 - x^23*y^25 - 2*x^14*y^33 + x^13*y^33 - 2*x^7*y^39 + x^27*y^10 + 2*x^26*y^10 + x^20*y^16

and one over GF(7):

sage: R.<x,y> = GF(7)[]
sage: p=-3*x^47*y^24
sage: q=-3*x^47*y^37 - 3*x^24*y^49 + 2*x^56*y^8 + 3*x^29*y^15 - x^2*y^33
sage: f=p*q
sage: f-f.factor(proof=False)
2*x^94*y^61 + 2*x^71*y^73 + x^103*y^32 - 2*x^59*y^61 - 2*x^76*y^39 - 2*x^36*y^73 + 3*x^49*y^57 - x^68*y^32 + 2*x^41*y^39 - 3*x^14*y^57

Examples can be constructed at will with the following code (change GF(7) by whatever you want):

R.<x,y> = GF(7)[]
nterms=2
for d in range(1,10^6):
   print d
   sys.stdout.flush()
   p = R.random_element(degree=d,terms=nterms)
   while p.degree()<=0:
      p = R.random_element(degree=d,terms=nterms)
   q = R.random_element(degree=d,terms=nterms)
   while q.degree()<=0:
      q = R.random_element(degree=d,terms=nterms)
   f = p*q
   lp = p.factor(proof=False)
   lq = q.factor(proof=False)
   lf = f.factor(proof=False)
   if lp*lq <> lf:
      print p, q
      raise ValueError

comment:10 Changed 9 years ago by zimmerma

  • Cc malb SimonKing added

comment:11 Changed 9 years ago by zimmerma

  • Keywords sd34 added

comment:12 Changed 9 years ago by malb

  • Dependencies set to #10903

I just tried all examples of this ticket with #10903 applied and they seem to return correct answers. I suggest we make this ticket dependent on #10903 and add Paul's examples as tests in this ticket.

comment:13 follow-up: Changed 9 years ago by malb

  • Authors set to Martin Albrecht, Paul Zimmermann
  • Status changed from new to needs_review

The attached patch removes all proof=False from multivariate polynomial factor() calls (being bold!) and adds examples from this ticket as doctests. Paul, can you install #11339, #10903 and this patch and try to break it?

comment:14 in reply to: ↑ 13 Changed 9 years ago by zimmerma

Replying to malb:

The attached patch removes all proof=False from multivariate polynomial factor() calls (being bold!) and adds examples from this ticket as doctests. Paul, can you install #11339, #10903 and this patch and try to break it?

the 2nd patch from #11339 fails to apply on 4.7.1:

sage: hg_sage.import_patch("/tmp/trac_11339_refcount_singular_polynomials.patch")
cd "/localdisk/tmp/install/sage/devel/sage" && hg status
cd "/localdisk/tmp/install/sage/devel/sage" && hg status
cd "/localdisk/tmp/install/sage/devel/sage" && hg import   "/tmp/trac_11339_refcount_singular_polynomials.patch"
applying /tmp/trac_11339_refcount_singular_polynomials.patch
patching file sage/rings/polynomial/multi_polynomial_libsingular.pyx
Hunk #12 FAILED at 765
Hunk #13 FAILED at 783
Hunk #15 FAILED at 820
Hunk #16 FAILED at 862
Hunk #17 FAILED at 883
Hunk #18 succeeded at 832 with fuzz 2 (offset -72 lines).
5 out of 103 hunks FAILED -- saving rejects to file sage/rings/polynomial/multi_polynomial_libsingular.pyx.rej
abort: patch failed to apply

I could try 4.7.2.alpha, where can I download it?

Paul

comment:16 Changed 9 years ago by zimmerma

  • Status changed from needs_review to needs_work
  • Work issues set to spkg fails to build

Martin, with 4.7.2.alpha3 the two patches from #11339 apply ok, but the new skpg fails to compile (on a 64-bit Core2 under Ubuntu):

...
make install in Singular
make[2]: Entering directory `/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers/src/Singular'
svnversion >svnver
svnversion: relocation error: /usr/lib/libldap_r-2.4.so.2: symbol gnutls_certificate_get_x509_cas, version GNUTLS_1_4 not defined in file libgnutls.so.26 with link time reference
make[2]: *** [svnver] Error 127
make[2]: Leaving directory `/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers/src/Singular'
make[1]: *** [install] Error 1
make[1]: Leaving directory `/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers/src'
make: *** [/localdisk/tmp/install/sage/local/bin/Singular-3-1-3] Error 2
Unable to build Singular.

real    5m33.608s
user    4m24.880s
sys     0m15.360s
sage: An error occurred while installing singular-3-1-3.svn-algnumbers
Please email sage-devel http://groups.google.com/group/sage-devel
explaining the problem and send the relevant part of
of /localdisk/tmp/install/sage/install.log.  Describe your computer, operating system, etc.
If you want to try to fix the problem yourself, *don't* just cd to
/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers and type 'make check' or whatever is appropriate.
Instead, the following commands setup all environment variables
correctly and load a subshell for you to debug the error:
(cd '/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers' && '/localdisk/tmp/install/sage/sage' -sh)
When you are done debugging, you can type "exit" to leave the
subshell.

Any clue?

Paul

comment:18 Changed 9 years ago by zimmerma

  • Work issues changed from spkg fails to build to Proof=... still present

I finally managed to apply the 4 patches, I ran sage -b, then installed the spkg, then ran sage -b again.

However Proof=... seems to be still present somewhere:

sage: R.<x,y> = GF(2)[]
sage: p=x^8 + y^8; q=x^2*y^4 + x; f=p*q
sage: f.factor(proof=False)
x * (x + y)^8 * (x*y^4 + 1)
sage: f.factor()
...
NotImplementedError: proof = True factorization not implemented.  Call factor with proof=False.

Paul

comment:19 Changed 9 years ago by malb

for the proof thingy you'll also need to apply the patch from this ticket, i.e.,trac_10902_factor_fixed.patch

comment:20 Changed 8 years ago by zimmerma

it seems to work much better (no bug found so far) but some factorizations are very slow (or hang), for example:

sage: K=GF(4,'a')
sage: a=K.gens()[0]
sage: R.<x,y> = K[]
sage: f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45 
sage: f.factor()

comment:21 Changed 8 years ago by malb

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Summary changed from missing terms in factorization of multivariate polynomials to proof=False unnecessary in factor()
  • Work issues Proof=... still present deleted

comment:22 Changed 8 years ago by malb

I've rebased the patch to 5.0.beta13 and made sure that sig_on/sig_off are always called, so that one can interrupt the factorisation if it hangs.

comment:23 Changed 8 years ago by zimmerma

Sage 5.0.beta13 fails to build on my computer, thus I'll have to wait for beta14 to review that ticket...

Paul

comment:24 Changed 8 years ago by zimmerma

thanks to Jeroen, I've managed to build Sage 5.0.beta13. However the issue reported in comment 20 is still present, whereas it took about one second in Sage 4.8:

sage: K=GF(4,'a')                                                          
sage: a=K.gens()[0]
sage: R.<x,y> = K[]
sage: f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45
sage: time r=f.factor(proof=False)
Time: CPU 1.08 s, Wall: 1.23 s
sage: r
y^17 * x^32 * (y^67 + x^60) * ((a + 1)*x^113 + y^28)

I'll be happy when this will be reported in another ticket.

Paul

comment:26 Changed 8 years ago by zimmerma

  • Status changed from needs_review to needs_work
  • Work issues set to doctest failure

one doctest fails with sage-5.0.beta13:

tarte% ../../../sage -t devel/sage-10902/sage/categories/quotient_fields.py
...

Expected:
    Traceback (most recent call last):
    ...
    NotImplementedError: proof = True factorization not implemented.  Call factor with proof=False.
Got:
    (x + y)^-1 * y * x

Paul

Changed 8 years ago by malb

comment:27 Changed 8 years ago by malb

  • Keywords sd34 removed
  • Status changed from needs_work to needs_review
  • Work issues doctest failure deleted

I've updated the patch.

comment:28 Changed 8 years ago by zimmerma

Martin, why did you remove the sd34 keyword? I had put it since I worked on this ticket during SD34.

Paul

comment:29 Changed 8 years ago by malb

  • Keywords sd34 added

Oh, I figured I should remove it since it wasn't resolved at SD34. I added it back.

comment:30 Changed 8 years ago by zimmerma

  • Authors changed from Martin Albrecht, Paul Zimmermann to Martin Albrecht
  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to positive_review

good work, thanks Martin!

Paul

PS: I removed my name as author since the patch is entirely from you.

comment:31 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.0 to sage-5.1

comment:32 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.1.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.