search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 480 forks source link

Since 8.7.beta3, giacpy_sage fails some groebner bases-related testdocs. #27306

Closed 7822f248-ba56-45f1-ab3d-4de7482bdf9f closed 5 years ago

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 5 years ago 
**********************************************************************
File "src/sage/libs/giac.py", line 187, in sage.libs.giac.?
Failed example:
    B.is_groebner() # optional - giacpy_sage
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/libs/giac.py", line 197, in sage.libs.giac.?
Failed example:
    B.is_groebner()                                             # optional - giacpy_sage
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/libs/giac.py", line 199, in sage.libs.giac.?
Failed example:
    B.ideal() == I.elimination_ideal([P.gen(0), P.gen(2)])      # optional - giacpy_sage
Expected:
    True
Got:
    False
**********************************************************************

Reported here, no further details (I'm out of my zone of competence).

Upstream: Fixed upstream, but not in a stable release.

CC: @frederichan-IMJPRG @sagetrac-parisse @slel

Component: interfaces: optional

Keywords: giacpy_sage, groebner bases, upgrade

Author: Frederic Han

Branch: 0c7c09c

Reviewer: Travis Scrimshaw, Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/27306

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 5 years ago

Changed keywords from none to giacpy_sage, groebner bases

frederichan-IMJPRG commented 5 years ago
comment:3

I suspect that it is not related to giacpy_sage. The output of the giac library has changed with this new version of giac (terms of index 40 and 24 of the sequence) :

sage: from sage.libs.giac import groebner_basis as gb_giac # optional - giacpy_sage
....: P = PolynomialRing(GF(previous_prime(2**31)), 6, 'x') # optional - giacpy_sage
....: I = sage.rings.ideal.Cyclic(P) # optional - giacpy_sage
....: B=gb_giac(I.gens());B # optional - giacpy_sage
....: B.is_groebner()  # Now is false
....: P.inject_variables()
....: old24=x2*x3^2*x5^3 - 477218588*x3^3*x5^3 - 477218590*x1*x2*x4*x5^3 - 1073741823*x2^2*x4*x5^3 - 1193
....: 04651*x1*x3*x4*x5^3 + 119304641*x2*x3*x4*x5^3 + 357913939*x3^2*x4*x5^3 - 715827881*x1*x4^2*x5^3 - 1
....: 073741823*x2*x4^2*x5^3 - 954437183*x3*x4^2*x5^3 - 477218588*x4^3*x5^3 - 835132526*x1*x2*x5^4 - 2386
....: 09293*x2^2*x5^4 - 357913943*x1*x3*x5^4 - 1073741820*x2*x3*x5^4 + 715827882*x3^2*x5^4 + 357913945*x1
....: *x4*x5^4 - 954437173*x2*x4*x5^4 + 238609295*x3*x4*x5^4 - x1*x5^5 - 954437174*x2*x5^5 + 715827881*x3
....: *x5^5 - 835132526*x4*x5^5 + 835132529*x5^6 + 835132529
....: old40=x1*x2*x3 + x2*x3^2 + 1073741821*x1*x2*x4 + 1073741822*x2^2*x4 + x1*x3*x4 + 1073741823*x2*x3*x
....: 4 + 2*x3^2*x4 + 1073741822*x2*x4^2 + x3*x4^2 + x1*x2*x5 + x2^2*x5 - 1073741823*x1*x3*x5 - x2*x3*x5 
....: - x3^2*x5 - x1*x4*x5 + 1073741823*x2*x4*x5 + x3*x4*x5 + x2*x5^2 - x3*x5^2
....: 
/home/fred-dev/sage/develop/sage.develop/local/lib/python2.7/site-packages/sage/libs/giac.py:125: DeprecationWarning: the module sage.matrix.matrix is deprecated
See http://trac.sagemath.org/24096 for details.
  with GiacSettingsDefaultContext():
// Giac share root-directory:/home/fred-dev/sage/develop/sage.develop/local/share/giac/
// Giac share root-directory:/home/fred-dev/sage/develop/sage.develop/local/share/giac/
Help file /home/fred-dev/sage/develop/sage.develop/local/share/giac/doc/fr/aide_cas not found
Added 0 synonyms
// Groebner basis computation time 0.006197 Memory 0.230032M
Polynomial Sequence with 45 Polynomials in 6 Variables
False
Defining x0, x1, x2, x3, x4, x5
sage: B[40]-old40
-2*x1*x3*x5
sage: B[24]-old24
-2*x2^2*x4*x5^3 - 2*x2*x4^2*x5^3
sage: C=[ j for j in B]
sage: C[40]=old40
sage: C[24]=old24
sage: from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence
sage: PolynomialSequence(C,P)
Polynomial Sequence with 45 Polynomials in 6 Variables
sage: PolynomialSequence(C,P).is_groebner()
True

I will report this on xcas forum

jdemeyer commented 5 years ago

Description changed:

--- 
+++ 
@@ -1 +1,30 @@
+
+```
+**********************************************************************
+File "src/sage/libs/giac.py", line 187, in sage.libs.giac.?
+Failed example:
+    B.is_groebner() # optional - giacpy_sage
+Expected:
+    True
+Got:
+    False
+**********************************************************************
+File "src/sage/libs/giac.py", line 197, in sage.libs.giac.?
+Failed example:
+    B.is_groebner()                                             # optional - giacpy_sage
+Expected:
+    True
+Got:
+    False
+**********************************************************************
+File "src/sage/libs/giac.py", line 199, in sage.libs.giac.?
+Failed example:
+    B.ideal() == I.elimination_ideal([P.gen(0), P.gen(2)])      # optional - giacpy_sage
+Expected:
+    True
+Got:
+    False
+**********************************************************************
+```
+
 Reported [here](https://groups.google.com/d/msg/sage-release/0QvdNonpGEg/SfQHQ6ejAQAJ), no further details (I'm out of my zone of competence).
frederichan-IMJPRG commented 5 years ago
comment:6

So I have asked there: https://xcas.univ-grenoble-alpes.fr/forum/viewtopic.php?f=3&t=2278 it is an overflow problem for primes between 2^30 and 2^31.

there is a fix of the giac library here https://dev.geogebra.org/trac/changeset/66972/

so we can either patch giac package or put a limitation to 2^30 instead of 2^31 in the function groebner_basis of

src/sage/libs/giac.py

what do you prefer?

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 5 years ago

Upstream: Fixed upstream, but not in a stable release.

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 5 years ago
comment:7

Replying to @frederichan-IMJPRG:

So I have asked there: https://xcas.univ-grenoble-alpes.fr/forum/viewtopic.php?f=3&t=2278 it is an overflow problem for primes between 2^30 and 2^31.

there is a fix of the giac library here https://dev.geogebra.org/trac/changeset/66972/

so we can either patch giac package or put a limitation to 2^30 instead of 2^31 in the function groebner_basis of

src/sage/libs/giac.py

what do you prefer?

Since I do not speak C++ fluently, I do not really understand the "fix", which seems to specify the type of the constant 2 : does this change the result of the comparison to "env" ?

If I understand correctly Bernard Parisse's answer, he plans to fix it someday in the upstream source (but no promises...).

So, in either case, we should be reminded of re-examining the situation (and possibly removing "our" fix) when the relevant part of (upstream) giac changes. In other words, we need a wake-up call...

Changing "our" giac.py sounds simpler (no patch of the upstream source), but will stay applied even when this limitation to integers <2**30 will cease to be relevant.

OTOH, if/when Bernard changes his source, a patch to the upstream source (more complicated) will no longer apply cleanly ... and we'll get our wake-up call.

Hence my ultimate preference for this solution.

I also update the ticket to frederichan's informal "report upstream" and the informal answer.

jdemeyer commented 5 years ago
comment:8

Replying to @EmmanuelCharpentier:

Since I do not speak C++ fluently, I do not really understand the "fix", which seems to specify the type of the constant 2 : does this change the result of the comparison to "env" ?

Yes. If a and b are of type int, then a comparison like a * 2 > b can give wrong results if 2 * a overflows (as int value). By changing this to a * 2LL > b, comparisons are done using long long which won't overflow (assuming that the type long long is large enough).

For the record, this check could also be rewritten as a > b / 2 but I don't know what is optimized best by the compiler.

If I understand correctly Bernard Parisse's answer, he plans to fix it someday in the upstream source (but no promises...).

Isn't the patch he posted a fix to the upstream source?

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 5 years ago
comment:9

Replying to @jdemeyer:

Replying to @EmmanuelCharpentier:

Since I do not speak C++ fluently, I do not really understand the "fix", which seems to specify the type of the constant 2 : does this change the result of the comparison to "env" ?

Yes. If a and b are of type int, then a comparison like a * 2 > b can give wrong results if 2 * a overflows (as int value). By changing this to a * 2LL > b, comparisons are done using long long which won't overflow (assuming that the type long long is large enough).

Thanks a lot ! Now, I understand why I did not understand... ;-]

For the record, this check could also be rewritten as a > b / 2 but I don't know what is optimized best by the compiler.

If I understand correctly Bernard Parisse's answer, he plans to fix it someday in the upstream source (but no promises...).

Isn't the patch he posted a fix to the upstream source?

The patch is somewhere in geogebra source tree. As far as I know, that's not giac's primary source tree.

Furthermore, his answer alludes to a forthcoming validation of (which ?) computation on Groebner bases and (grandiose) plans of using them to compute something called cyclic10. All these things are related in his discourse, so I thought he was alluding to (larger) changes in giac's handling of Groebner bases.

2edf2d52-6c17-4f2a-88a6-e860db4dcddf commented 5 years ago
comment:10

Yes. In short, I have made some changes in Groebner basis computations to improve speed for multiples CPU architectures. They are not yet fully tested, therefore I did not update the stable source tarball, but the unstable tarball on my site is up to date with the overflow fix. I have also committed the overflow fix to geogebra SVN tree.

frederichan-IMJPRG commented 5 years ago
comment:11

starting a branch.

New commits:

c2b56daFix giac gbasis overflow pb with big primes; remove sunos patch because it is already in upstream source. clean offsets in patches
frederichan-IMJPRG commented 5 years ago

Commit: c2b56da

frederichan-IMJPRG commented 5 years ago

Branch: public/giac-trac27306

frederichan-IMJPRG commented 5 years ago

Description changed:

--- 
+++ 
@@ -28,3 +28,7 @@

Reported here, no further details (I'm out of my zone of competence). + +* New upstream giacpy_sage tarball to put in upstream: +http://webusers.imj-prg.fr/~frederic.han/xcas/giacpy/sage/giacpy_sage-0.6.7.tar.gz +

frederichan-IMJPRG commented 5 years ago
comment:12

Also this bug is not giacpy_sage related, there is a doctest in giacpy_sage that needs to be upgraded due to a the upgrade of giac. So I have made a new upstream version of giacpy_sage with this doctest fix and I have also added some new keywords supported by this new giac version.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from c2b56da to 719c662

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

719c662update giacpy_sage to 0.6.7; update giac keywords to 1.5.x and fix 1 change of output in doctest
frederichan-IMJPRG commented 5 years ago
comment:14

the small patch to the giac library looks to fix the problem for me (linux fedora amd64)

tscrim commented 5 years ago
comment:15

I believe our convention is anytime there is patches to put a .p0 to indicate that. Otherwise I think this is good, but would like a test on another OS (mine is Linux Ubuntu Intel i7), preferably OSX (but I am probably being overly paranoid).

jdemeyer commented 5 years ago
comment:16

Don't forget Author name.

frederichan-IMJPRG commented 5 years ago

Author: Frederic Han

jdemeyer commented 5 years ago
comment:18

Why are you removing build/pkgs/giac/patches/sunos_abs.patch? Apart from that and the version number issue, this is good for me.

jdemeyer commented 5 years ago

Reviewer: Travis Scrimshaw, Jeroen Demeyer

frederichan-IMJPRG commented 5 years ago
comment:20

Replying to @jdemeyer:

Why are you removing build/pkgs/giac/patches/sunos_abs.patch? Apart from that and the version number issue, this is good for me.

because I saw on line 24 in rpn.h:

#undef _ABS // for SunOS

so it looks included upstream.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 719c662 to 0c7c09c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

0c7c09cbump giac package name to 1.5.0.37.p0
jdemeyer commented 5 years ago
comment:22

Replying to @frederichan-IMJPRG:

Replying to @jdemeyer:

Why are you removing build/pkgs/giac/patches/sunos_abs.patch? Apart from that and the version number issue, this is good for me.

because I saw on line 24 in rpn.h:

#undef _ABS // for SunOS

so it looks included upstream.

Right, that makes sense.

tscrim commented 5 years ago
comment:24

Let's send this off to the buildbots now.

vbraun commented 5 years ago

Changed branch from public/giac-trac27306 to 0c7c09c

slel commented 5 years ago
comment:26

Adding keyword "upgrade" to indicate the need to upload the tarball to the master download mirror, so it gets mirrored on our download mirror network.

slel commented 5 years ago

Changed commit from 0c7c09c to none

slel commented 5 years ago

Changed keywords from giacpy_sage, groebner bases to giacpy_sage, groebner bases, upgrade