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 )
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)
Change History (33)
comment:1 follow-up: ↓ 2 Changed 9 years ago by
comment:2 in reply to: ↑ 1 Changed 9 years ago by
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: ↓ 4 Changed 9 years ago by
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
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
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: ↓ 7 Changed 9 years ago by
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
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
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
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
- Cc malb SimonKing added
comment:11 Changed 9 years ago by
- Keywords sd34 added
comment:12 Changed 9 years ago by
- Dependencies set to #10903
comment:13 follow-up: ↓ 14 Changed 9 years ago by
- Status changed from new to needs_review
comment:14 in reply to: ↑ 13 Changed 9 years ago by
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:15 Changed 9 years ago by
Yes, you'll need 4.7.2.alpha3:
http://boxen.math.washington.edu/home/release/sage-4.7.2.alpha3/sage-4.7.2.alpha3.tar
comment:16 Changed 9 years ago by
- 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:17 Changed 9 years ago by
The new SPKG should fix this issue.
http://sage.math.washington.edu/home/malb/spkgs/singular-3-1-3-3.spkg
comment:18 Changed 9 years ago by
- 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
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
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
- 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
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
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
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:25 Changed 8 years ago by
I've created http://trac.sagemath.org/sage_trac/ticket/12846
comment:26 Changed 8 years ago by
- 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
comment:27 Changed 8 years ago by
- 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
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
- 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
- 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
- Milestone changed from sage-5.0 to sage-5.1
comment:32 Changed 8 years ago by
- Merged in set to sage-5.1.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
I reported this upstream: http://www.singular.uni-kl.de:8002/trac/ticket/320