[sage-devel] A Sage interface for FGb (Gröbner bases)

[Markus Wageringel]

Hi everyone.

I created a Sage wrapper for the C interface of FGb, which makes it easy to
call FGb from within Sage. The sources are available on Github [1] and can
be installed as a Python package into Sage:

[1] https://github.com/mwageringel/fgb_sage


FGb is a C-library by J. C. FaugÚre for computing Gröbner bases and
supposedly it is one of the faster implementations that exist. It is
included with Maple [2]. FGb is closed source, but comes with a C interface
that is freely distributed for academic use. Some of the features:

• The computations run in parallel. (This only seems to work for
computations over finite fields.)
• Elimination/block orders are supported.
• It runs on Linux and Mac. (There seem to be some issues, though. I could
not get FGb to work on my Ubuntu machine. It fails with an "Illegal
instruction" error.)


In my Sage interface, I implemented just two functions: computing Gröbner
bases and elimination ideals. Supposedly, the FGb C-library supports other
functionality like computing Hilbert polynomials, but that part of the
library is not documented very well, so it does not make sense to try to
create wrappers for that. The focus is finding a Gröbner basis which, once
computed, can be used by Sage for further computations.

I just wanted to share this. Maybe it is useful for someone.

Markus

[2] https://www-polsys.lip6.fr/~jcf/FGb/Maple/index.html

['Martin R. Albrecht' via sage-devel]

Hi Markus,

Works without a hitch here (Debian/testing, Sage 8.4). I have been planning on doing this over the years but never got around to it, so really cool to see that you did. Nice work!

Cheers,
Martin

Post by Markus Wageringel
Hi everyone.
I created a Sage wrapper for the C interface of FGb, which makes it easy to
call FGb from within Sage. The sources are available on Github [1] and can
[1] https://github.com/mwageringel/fgb_sage
FGb is a C-library by J. C. Faugère for computing Gröbner bases and
supposedly it is one of the faster implementations that exist. It is
included with Maple [2]. FGb is closed source, but comes with a C interface
• The computations run in parallel. (This only seems to work for
computations over finite fields.)
• Elimination/block orders are supported.
• It runs on Linux and Mac. (There seem to be some issues, though. I could
not get FGb to work on my Ubuntu machine. It fails with an "Illegal
instruction" error.)
In my Sage interface, I implemented just two functions: computing Gröbner
bases and elimination ideals. Supposedly, the FGb C-library supports other
functionality like computing Hilbert polynomials, but that part of the
library is not documented very well, so it does not make sense to try to
create wrappers for that. The focus is finding a Gröbner basis which, once
computed, can be used by Sage for further computations.
I just wanted to share this. Maybe it is useful for someone.
Markus
[2] https://www-polsys.lip6.fr/~jcf/FGb/Maple/index.html

--
_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: ***@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

[Thierry]

Hi,

Post by 'Martin R. Albrecht' via sage-devel
Hi Markus,
Works without a hitch here (Debian/testing, Sage 8.4). I have been planning on doing this over the years but never got around to it, so really cool to see that you did. Nice work!

It was on my todo list for a while too, since our implementations are very
slow. Here "very" means "prohibitively", since some systems can not be
solved with Sage in decent time (via Singular), while FGb could solve them
quickly. A colleague of mine had to do a lot of tricks to solve a research
problem with Sage, and was disapointed when he discovered that FGb could
have saved him hours of hard work during a seminar, where a Maple user
showed him the Groebner basis. See also the related questions on
ask.sagemath.org for concrete examples.

Unfortunately, the fact that is is neither free-software nor open-source
made it lower on my todo list. I wonder whether it could be possible to
kindly ask J.C. Faugere to free his code, especially since his work on
this is founded by the (french) public service.

Thanks a lot for the work !

Ciao,
Thierry

Post by 'Martin R. Albrecht' via sage-devel
Cheers,
Martin

Post by Markus Wageringel
Hi everyone.
I created a Sage wrapper for the C interface of FGb, which makes it easy to
call FGb from within Sage. The sources are available on Github [1] and can
[1] https://github.com/mwageringel/fgb_sage
FGb is a C-library by J. C. Faugère for computing Gröbner bases and
supposedly it is one of the faster implementations that exist. It is
included with Maple [2]. FGb is closed source, but comes with a C interface
• The computations run in parallel. (This only seems to work for
computations over finite fields.)
• Elimination/block orders are supported.
• It runs on Linux and Mac. (There seem to be some issues, though. I could
not get FGb to work on my Ubuntu machine. It fails with an "Illegal
instruction" error.)
In my Sage interface, I implemented just two functions: computing Gröbner
bases and elimination ideals. Supposedly, the FGb C-library supports other
functionality like computing Hilbert polynomials, but that part of the
library is not documented very well, so it does not make sense to try to
create wrappers for that. The focus is finding a Gröbner basis which, once
computed, can be used by Sage for further computations.
I just wanted to share this. Maybe it is useful for someone.
Markus
[2] https://www-polsys.lip6.fr/~jcf/FGb/Maple/index.html

--
_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[parisse]

Post by Thierry
Hi,
It was on my todo list for a while too, since our implementations are very
slow. Here "very" means "prohibitively", since some systems can not be
solved with Sage in decent time (via Singular), while FGb could solve them
quickly.

That's not correct, Sage has a wrapper to Giac which has fast GB code and
is also open-source. I really wonder why it seems to be ignored.

[Dima Pasechnik]

Post by Thierry
Hi,
It was on my todo list for a while too, since our implementations are very
slow. Here "very" means "prohibitively", since some systems can not be
solved with Sage in decent time (via Singular), while FGb could solve them
quickly.

That's not correct, Sage has a wrapper to Giac which has fast GB code and is also open-source. I really wonder why it seems to be ignored.

From Sage-centric point of view, one reason for this is that
commutative algebra in Sage is a mess, and the multivariate polynomial
backend hardcodes Singular.

I (and many others - e.g. people really want Macaulay2 advanced
functionality, e.g. resolutions, available) really would like to see
an improvement here.

Where and how do we even start fixing this?

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[mmarco]

I would be interested in that too, but that sounds like a complex task. I
think one or more GSoC projects could fit into that... and maybe also some
thematic Sage Days.

El jueves, 22 de noviembre de 2018, 11:28:32 (UTC+1), Dima Pasechnik

Post by parisse

Post by Thierry
Hi,
It was on my todo list for a while too, since our implementations are

very

Post by parisse

Post by Thierry
slow. Here "very" means "prohibitively", since some systems can not be
solved with Sage in decent time (via Singular), while FGb could solve

them

Post by parisse

Post by Thierry
quickly.

That's not correct, Sage has a wrapper to Giac which has fast GB code

and is also open-source. I really wonder why it seems to be ignored.
From Sage-centric point of view, one reason for this is that
commutative algebra in Sage is a mess, and the multivariate polynomial
backend hardcodes Singular.
I (and many others - e.g. people really want Macaulay2 advanced
functionality, e.g. resolutions, available) really would like to see
an improvement here.
Where and how do we even start fixing this?

Post by parisse
--
You received this message because you are subscribed to the Google

Groups "sage-devel" group.

Post by parisse
To unsubscribe from this group and stop receiving emails from it, send

<javascript:>.

Post by parisse
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Dima Pasechnik]

I would be interested in that too, but that sounds like a complex task. I think one or more GSoC projects could fit into that... and maybe also some thematic Sage Days.

It's not a GSoC project, as it's 1st of all redesigning the
corresponding class/category structures to make it meaningful. I don't
know enough about Sage's category framework (and only barely enough
commutative algebra, to be honest)
to be a leader on this...

Post by Dima Pasechnik

Post by Thierry
Hi,
It was on my todo list for a while too, since our implementations are very
slow. Here "very" means "prohibitively", since some systems can not be
solved with Sage in decent time (via Singular), while FGb could solve them
quickly.

That's not correct, Sage has a wrapper to Giac which has fast GB code and is also open-source. I really wonder why it seems to be ignored.

From Sage-centric point of view, one reason for this is that
commutative algebra in Sage is a mess, and the multivariate polynomial
backend hardcodes Singular.
I (and many others - e.g. people really want Macaulay2 advanced
functionality, e.g. resolutions, available) really would like to see
an improvement here.
Where and how do we even start fixing this?

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

['Martin R. Albrecht' via sage-devel]

Post by parisse

Post by Thierry
Hi,
It was on my todo list for a while too, since our implementations are very
slow. Here "very" means "prohibitively", since some systems can not be
solved with Sage in decent time (via Singular), while FGb could solve them
quickly.

That's not correct, Sage has a wrapper to Giac which has fast GB code and
is also open-source. I really wonder why it seems to be ignored.

Hi,

speaking of Giac (sorry, if this should rather be on sage-support or off-list):

Can I get the degree reached during the computation and the sizes of the matrices considered out somehow?

Rationale: In crypto, we usually want to see if the system under consideration behaves like a random-system despite not being one. One way of testing this is to compute the degree of semi-regularity for a semi-regular sequence and compare with the degree reached during a GB computation of an actual instance.

Cheers,
Martin
--
_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: ***@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

[parisse]

Post by 'Martin R. Albrecht' via sage-devel
Hi,
Can I get the degree reached during the computation and the sizes of the
matrices considered out somehow?

export GIAC_DEBUG=2
before calling giac will display some information on the intermediate
computations

[Jean-Pierre Flori]

For GB addict, yet another open source implementation:
https://gforge.inria.fr/projects/tinygb/

[Friedrich Wiemer]

Cool Markus, thanks a lot for sharing this! :)


Am Donnerstag, 22. November 2018 10:11:39 UTC+1 schrieb Thierry

Post by Thierry
Unfortunately, the fact that is is neither free-software nor open-source
made it lower on my todo list. I wonder whether it could be possible to
kindly ask J.C. Faugere to free his code, especially since his work on
this is founded by the (french) public service.

That would be really nice!

[parisse]

Did you make some comparisons with Giac ?

Some benchmarks from Roman Pearce and my own tests, about 2 years old.

Roman used an Intel Core i5 4570 3.2 GHz with 8 GB DDR3-1600 running 64-bit
Linux (4 cores, 4 threads, 6M cache, turbo 3.2 -> 3.6GHz). I also checked
Giac on my Mac (Core i5 2.9Ghz, 2 cores, 4 threads)

Groebner bases mod p are computed for the fastest machine prime supported
by each software.

For mgb and Singular p=2^31-1, for Magma p=11863279, for FGb p=65521, and
for Giac p=16777213.

Zp mgb 8b Magma FGb Giac Singular 4.0.2 Giac
on my Mac 1 thread [2 threads]
cyclic8 0.715 0.970 2.050 3.123 37.490
3.13 [2.61]
cyclic9 41.157 48.860 221.890 179.689 7113.800 282-287
[195]
katsura12 2.787 3.680 37.830 24.863 651.790 33
[23.3]
katsura13 16.269 21.080 314.640 184.403 5187.580 247.6
[167.5]
bayes148 15.754 16.520 891.400 1206.892 5.160 97.5
[86]
gametwo7 4.701 6.070 24.220 68.336 485.750 48.2
[38.9]
jason210 2.789 3.180 32.990 12.570 1.790 10.8
[10.5]
mayr42 36.755 30.780 196.530 4087.811 185.760 146.6
[142.6]
yang1 17.347 15.900 494.440 - 90.260 193.8
[191]

Q mgb 8b Magma FGb Giac Singular
cyclic7 0.979 0.640 1.750 0.951 16.288 (Mac 19) 1.61
[1.10]
cyclic8 12.290 14.750 42.690 25.892 685.352? 49.5
[30.0] (this one has been improved recently)
katsura10 4.740 2.270 7.870 3.858 203.529? 5.17 [3.79]
katsura11 34.180 17.130 50.220 24.437 1635.524? 41.8
[27.5]
alea6 50.620 114.680 88.470 52.433 1273.341 72.8
[57.3]
eco12 21.140 31.030 62.580 22.765 3333.936 42.4
[29.0]
jason210 19.530 4.790 62.270 23.831 47.273?? 45.3
[29.3]
noon9 42.330 45.430 157.480 126.898 1483.740 121
[113]

[Markus Wageringel]

Thanks for the feedback everyone.

Post by parisse
Did you make some comparisons with Giac ?
Some benchmarks from Roman Pearce and my own tests, about 2 years old.

I have not done any comparisons, mainly because I cannot do anything about
the performance of FGb anyway. Moreover, to my knowledge, Giac does not
support elimination orders (at least the Sage interface does not), which
made it less suitable for my use cases.

I remember having seen those benchmarks before, but I cannot find them
anymore. If you send a copy of the polynomial systems, I can make some
rough comparisons of the options available within Sage.

Markus

[parisse]

Post by Markus Wageringel
Thanks for the feedback everyone.

Post by parisse
Did you make some comparisons with Giac ?
Some benchmarks from Roman Pearce and my own tests, about 2 years old.

I have not done any comparisons, mainly because I cannot do anything about
the performance of FGb anyway. Moreover, to my knowledge, Giac does not
support elimination orders (at least the Sage interface does not), which
made it less suitable for my use cases.

Giac supports double revlex ordering, this is the order used by the
eliminate command of Giac. Geogebra has many examples of eliminate commands
there https://dev.geogebra.org/trac/browser/trunk/geogebra/giac/src/test

I remember having seen those benchmarks before, but I cannot find them

Post by Markus Wageringel
anymore. If you send a copy of the polynomial systems, I can make some
rough comparisons of the options available within Sage.

https://www-fourier.ujf-grenoble.fr/~parisse/giac/examples/groebner/

[Markus Wageringel]

Post by parisse
Giac supports double revlex ordering, this is the order used by the
eliminate command of Giac. Geogebra has many examples of eliminate commands
there https://dev.geogebra.org/trac/browser/trunk/geogebra/giac/src/test

Nice. It would probably be good to have this function in the Sage interface
for giac, as well. Is it also possible to obtain the full Gröbner basis
with respect to the revlex/revlex block order, but without elimination?



Meanwhile, Roman Pearce's website [5] is back online and I used those
polynomial systems to compare the Sage interfaces libsingular, giacpy_sage
and fgb_sage. I created a gist of the code [6].

Versions of libraries used:
• Sage 8.5.beta4
• libSingular-4.1.1
• giacpy_sage-0.6.6, giac-1.4.9.45.p4
• fgb_sage-0.1, fgb-20150719 (14538, 14539)

Primes used: singular: 2^31-1, giac: 16777213, fgb: 65521.

Machine: CentOS 7.5.1804, Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, 32
cores, 196 G memory.
Number of threads in parentheses. Computation time in seconds.

â„€/p | singular (1) | giac (4) giac (16) | fgb (4)
fgb (16)
cyclic8 | 62.01 | 7.71 4.88 | 1.86
1.38
cyclic9 | 11519.16 | 258.85 191.30 | 112.31
55.37
katsura11 | 107.91 | 12.62 11.10 | 4.04
2.43
katsura12 | 1090.37 | 67.07 60.25 | 23.09
12.59
bayes148 | 7.19 | 92.63 92.15 | 571.28
471.59
gametwo7 | 934.69 | 122.65 116.37 | 20.78
14.30
jason210 | 2.67 | 23.71 23.39 | 24.58
22.44
mayr42 | 124.74 | 169.94 166.56 | 139.12
111.08
yang1 | 49.79 | [3] [3] | 257.96
177.65

ℚ | singular (1) | giac (4) giac (16) | fgb (1)
cyclic7 | [1] | 10.71 10.62 | 4.20
cyclic8 | [2] | 120.44 205.57 | 77.22
katsura9 | 19.19 | 27.30 27.23 | 3.04
katsura10 | 236.62 | 241.32 238.23 | 18.58
alea6 | 35724.62 | 578.94 548.39 | [4] 331.64
eco12 | [1] | 4748.24 4811.32 | 102.06
jason210 | 13.43 | 65.24 83.82 | 49.38
noon9 | 132.82 | 3146.97 3159.49 | 136.55

I am a bit surprised about some of the Singular results being a lot worse
than reported in [5], cyclic7 in particular. Perhaps starting this
computation with some different options can help here.

[1] Aborted after 13.5 hours.
[2] Skipped.
[3] Error, problem too large.
[4] Excessive memory usage of about 300 G; computed on a different machine.
[5] http://www.cecm.sfu.ca/~rpearcea/mgb.html
[6] https://gist.github.com/mwageringel/213a4a980e338ec8ea5a75482b1bcb2b

['Bill Hart' via sage-devel]

Post by Markus Wageringel
I am a bit surprised about some of the Singular results being a lot worse
than reported in [5], cyclic7 in particular. Perhaps starting this
computation with some different options can help here.
<SNIP>
[5] http://www.cecm.sfu.ca/~rpearcea/mgb.html

All the other systems are using modular methods here, so Roman use the
modstd library (the command is modStd) in Singular to get those timings.
Indeed cyclic7 over Q takes about 20s on my laptop in Singular using this
approach.

[parisse]

Post by Markus Wageringel

Post by parisse
Giac supports double revlex ordering, this is the order used by the
eliminate command of Giac. Geogebra has many examples of eliminate commands
there https://dev.geogebra.org/trac/browser/trunk/geogebra/giac/src/test

Nice. It would probably be good to have this function in the Sage
interface for giac, as well. Is it also possible to obtain the full Gröbner
basis with respect to the revlex/revlex block order, but without
elimination?

From giac, call gbasis with the list of polynomial and the list of the
first block indets.

Post by Markus Wageringel
Meanwhile, Roman Pearce's website [5] is back online and I used those
polynomial systems to compare the Sage interfaces libsingular, giacpy_sage
and fgb_sage. I created a gist of the code [6].
• Sage 8.5.beta4
• libSingular-4.1.1
• giacpy_sage-0.6.6, giac-1.4.9.45.p4

The timings on Q do not reflect the timings of native giac, there must be
some misconfiguration or something wrong with the sage interface. Higher
timings with 16 threads instead of 4 for a modular algorithm is suspicious.

[Markus Wageringel]

Post by 'Bill Hart' via sage-devel
All the other systems are using modular methods here, so Roman use the
modstd library (the command is modStd) in Singular to get those timings.
Indeed cyclic7 over Q takes about 20s on my laptop in Singular using this
approach.

Thanks for the hint. With that, I get the following times over ℚ.

ℚ | singular (4) singular (16)
cyclic7 | 28.79 21.27
cyclic8 | 1109.03 623.98
katsura9 | 28.07 25.14
katsura10 | 329.86 172.15
alea6 | 3053.70 2549.42
eco12 | 4879.15 1888.11
jason210 | 122.07 106.33
noon9 | 2339.98 1502.74

Post by 'Bill Hart' via sage-devel
From giac, call gbasis with the list of polynomial and the list of the
first block indets.

That worked. Thanks.


The timings on Q do not reflect the timings of native giac, there must be

Post by 'Bill Hart' via sage-devel
some misconfiguration or something wrong with the sage interface. Higher
timings with 16 threads instead of 4 for a modular algorithm is suspicious.

While there will be some overhead due to the conversion from and to Sage,
it is the same in both cases. In fact, I observe similar times with the
native Giac that is installed into the Sage environment, when applied to
the Giac input file cyclic8 you linked above [1]: 0m27.309s using 4 threads
and 1m43.493s using 16. Indeed, CPU usage rarely surpasses 400% during the
computation. I am not sure what could be wrong here. Perhaps it is
something related to the patches of the Giac in Sage [2]?

[1]
https://www-fourier.ujf-grenoble.fr/~parisse/giac/examples/groebner/cyclic8
[2] https://github.com/sagemath/sage/tree/8.5.beta6/build/pkgs/giac/patches

[parisse]

Post by Markus Wageringel
While there will be some overhead due to the conversion from and to Sage,
it is the same in both cases. In fact, I observe similar times with the
native Giac that is installed into the Sage environment, when applied to
the Giac input file cyclic8 you linked above [1]: 0m27.309s using 4 threads
and 1m43.493s using 16. Indeed, CPU usage rarely surpasses 400% during the
computation. I am not sure what could be wrong here. Perhaps it is
something related to the patches of the Giac in Sage [2]?

I do not have access to a server with that many CPU. In fact, I only have
access to my Mac with 2 threads. It is therefore possible that something
strange happens with 4 or 16 threads that I don't see with 2 threads. If
you can reproduce that with giac native without patch, then that's probably
what happens. But then why does it not scale to 4 or 16 threads? The
modular algorithm is very simple: compute the gbasis for n primes (this is
done in parallel), and chinese remainder after that (not parallelized). For
most of the examples in the benchmarks here, chinese remaindering is a
small percentage of the time required. This corresponds to the timings of
Roman Pearce http://www.cecm.sfu.ca/~rpearcea/mgb.html (4 threads).
Perhaps a memory problem? I mean, malloc/new in parallel may spend a lot of
time waiting for locks.

[Dima Pasechnik]

While there will be some overhead due to the conversion from and to Sage, it is the same in both cases. In fact, I observe similar times with the native Giac that is installed into the Sage environment, when applied to the Giac input file cyclic8 you linked above [1]: 0m27.309s using 4 threads and 1m43.493s using 16. Indeed, CPU usage rarely surpasses 400% during the computation. I am not sure what could be wrong here. Perhaps it is something related to the patches of the Giac in Sage [2]?

I do not have access to a server with that many CPU. In fact, I only have access to my Mac with 2 threads.

you can certainly get free cloud resources from Google, to spin out
Linux (and not only) VMs with many cores, they have a faculty
programme like this.
I've been using it since Sept.
https://cloud.google.com/edu/

It is therefore possible that something strange happens with 4 or 16 threads that I don't see with 2 threads. If you can reproduce that with giac native without patch, then that's probably what happens. But then why does it not scale to 4 or 16 threads? The modular algorithm is very simple: compute the gbasis for n primes (this is done in parallel), and chinese remainder after that (not parallelized). For most of the examples in the benchmarks here, chinese remaindering is a small percentage of the time required. This corresponds to the timings of Roman Pearce http://www.cecm.sfu.ca/~rpearcea/mgb.html (4 threads).
Perhaps a memory problem? I mean, malloc/new in parallel may spend a lot of time waiting for locks.
--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[parisse]

Post by Dima Pasechnik
you can certainly get free cloud resources from Google, to spin out
Linux (and not only) VMs with many cores, they have a faculty
programme like this.
I've been using it since Sept.
https://cloud.google.com/edu/

I don't think I'm eligible and even if I was, I don't want to depend from
google or any company for something like that (the risk of IP problems is
much too high and anyway I don't like the idea that private company should
replace public support for research). Either I can have ssh access to some
university linux server somewhere or this will be delayed until I buy
myself a laptop with more than 2 (reals) threads.

[Dima Pasechnik]

Post by parisse

Post by Dima Pasechnik
you can certainly get free cloud resources from Google, to spin out
Linux (and not only) VMs with many cores, they have a faculty
programme like this.
I've been using it since Sept.
https://cloud.google.com/edu/

I don't think I'm eligible

I think a MCF at a university in France would be as eligible as an
analogue of MCF
in a UK university, like me:
https://cloud.google.com/edu/?options=research-credits#options

Post by parisse
and even if I was, I don't want to depend from google or any company for something like that (the risk of IP problems is much too high

IP problems while working with open source software? Really?
(of course, companies that sell hardware and university system
administrators might be saying that cloud computing providers have
horns on their heads and make you sign off your soul with a
blood-filled pen...)

Post by parisse
and anyway I don't like the idea that private company should

replace public support for research). Either I can have ssh access to
some university linux server somewhere

The reality is that many universities already moved to renting servers
in datacenters, and this will become more and more prevalent. There
are universities in UK that do not have any servers at all, and run CS
education programs more or less fully in the cloud.
Just a couple of days ago I spoke to someone from U. of Portsmouth,
where every CS major students gets issued a linux VM at the beginning
of their study, and do most of their graded coursework there (at a
cost for the university for under 7 euro per student per year).

Post by parisse
or this will be delayed until I buy myself a laptop with more than 2 (reals) threads.

whereas you could run your tests on a 100-core VM, for free...

[Dima Pasechnik]

Efficient code does not depend on how you handle it (git, svn or

tarballs or whatever).
Efficiency of handling code does depend upon this; fixing a trivial
C++ issue in Giac takes 10 times longer (and takes 10 times more time
and effort from the community around Giac) than in a similar system
hosted, say, on github.

Let me remind you that Giac source code is available on Geogebra SVN.

this is not mentioned on Giac pages, and if I ever heard about it I
blissfully forgot. I did check a couple of times.
I take it that you either do not use svn at all or prefer outsiders not to
be aware of it.
What is the relation between giac source tarballs and that svn?

Obviously, I have better things to do than duplicating repositories,

especially if the handling software is not the same that the software I'm
used too.
If you want to fix an issue in my code, the fastest way is to send a bug
report on the Xcas forum. Then I usually fix the bug in a couple of days. I
don't understand how it could take 10 times more effort from the community.

I estimated the time it took to get patches needed for Giac to support
clang 6.0.1.
Several times I had to download Giac tarballs, tried to build etc,
only to discover that not all the things I reported were fixed, so I had to
produce new patches, report them again and again. Took hours, in total,
spread over several days.
Whereas with VCS in place and used right it should have taken minutes, not
hours.

Actually, I think you just want to coerce me to follow your rules. But

well, I have the opposite view than you, the way sage handles bug reports
and so would take me 10 * more time than the way I work.

no, I merely do not want to waste my time on you being unable to
efficiently utilise my work.
And I am sure I am not alone in this sentiment, it must be common among
people trying to help you to mak Giac better.
Thanks goodness you do not require changes to be mailed to you on floppy
disks :-)

And I don't think different practices is the real reason why Giac

was/is mostly ignored here.
When ODK proposal was being written, we still tried getting Giac to
stop changing distribution tarballs without bumping up version
numbers...

Pfff! My guess is that people were not really interested in giac (and did
not really check it) because they have access to magma when it comes to
large computations where giac has more efficient code than singular.
Ok, I'll stop here.

no, Magma is not common, especially outside the US. I never published
anything that used Magma.
(no, in fact once I did, my coauthors used error-correcting codes produced
by Magma).

Fortunately, there are constructive people in the community, I'd like to
thank Samuel LeliÚvre and William Stein who managed to open me an account
on a multi-CPU server.

I could have offered to open you an account on a multicore server, but it
would actually be a commercial cloud server, not a “university” server
(perhaps that’s what you actually got from Samuel and William :-)). I
cannot give anyone access to Oxford university servers, without lengthly
paperwork, and in the end it would be a 10-year old Linux cluster with
outdated software and hardware...

--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[parisse]

Giac on Geogebra SVN
<https://dev.geogebra.org/trac/browser/trunk/geogebra/giac/src/giac>
The giac tarball is self-contained for compiling on gnu systems. The stable
version corresponding to the latest debian packages is giac_stable.tgz
<https://www-fourier.ujf-grenoble.fr/~parisse/giac/giac_stable.tgz>
The latest unstable version is giac_unstable.tgz
<https://www-fourier.ujf-grenoble.fr/~parisse/giac/giac_unstable.tgz>
The geogebra svn has the same source files as the unstable tarball, but
it's not suitable for compile from scratch because they are using different
tools to compile (depending on targets, win/mac/linux desktop,
jni/javascript/android etc.).

I made a few changes to the way parallelization is called, and got some
progress. Now cyclic9 on Q takes a little more than 4h with 1 thread, 1h41
real time/4h40 CPU with 6 threads (probably not far from optimal).

[parisse]

Got cyclic9 on Q with 16 threads in 45 minutes real time (about 6h and 20
minutes CPU time).

I made a few changes to the way parallelization is called, and got some

Post by parisse
progress. Now cyclic9 on Q takes a little more than 4h with 1 thread, 1h41
real time/4h40 CPU with 6 threads (probably not far from optimal).

['Bill Hart' via sage-devel]

On Friday, 7 December 2018 07:53:18 UTC+1, Markus Wageringel wrote:

<SNIP>

While there will be some overhead due to the conversion from and to Sage,

Post by Markus Wageringel
it is the same in both cases. In fact, I observe similar times with the
native Giac that is installed into the Sage environment, when applied to
the Giac input file cyclic8 you linked above [1]: 0m27.309s using 4 threads
and 1m43.493s using 16. Indeed, CPU usage rarely surpasses 400% during the
computation. I am not sure what could be wrong here. Perhaps it is
something related to the patches of the Giac in Sage [2]?

How many physical cores do you have on the machine (not logical cores), and
how many CPU sockets and what is the cache structure? (I assume it is at
least 16 physical cores, but I'm asking more because this sort of thing
often happens because of shared caches.)

[Markus Wageringel]

Post by 'Bill Hart' via sage-devel
How many physical cores do you have on the machine (not logical cores),
and how many CPU sockets and what is the cache structure? (I assume it is
at least 16 physical cores, but I'm asking more because this sort of thing
often happens because of shared caches.)

It has 2 CPU sockets, each having 8 physical cores with 2 threads each. As
for the cache:

L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 20480K

Does this answer the question? Also, here is a specification:
https://ark.intel.com/products/64584/Intel-Xeon-Processor-E5-2660-20M-Cache-2-20-GHz-8-00-GT-s-Intel-QPI-

[john_perry_usm]

I walk into this discussion with some hesitancy, but Christian Eder has
developed a rather efficient F4 algorithm. [1] I know it works and is quite
fast, though I haven't compared it to the implementations mentioned above.
Unfortunately, I haven't heard from him in a while after he went off to
Iran for a few weeks, and he doesn't seem to have updated his site since
then, either.

Is integrating Eder's project something a group might be interested in
doing at [2]? I had planned to apply to work on integrating a similar
project at [2] (a different sort of F4-style Gröbner basis algorithm [3,4])
but perhaps [1] would be a good bet since there's no doubt about it and
Eder spent at least a year in Paris working with FaugÚre.

regards
john perry

[1] https://github.com/ederc/gb

[2] https://www.ima.umn.edu/2018-2019/SW7.22-26.19

[3] https://github.com/johnperry-math/DynGB

[4] https://dl.acm.org/citation.cfm?id=3087643

On Wednesday, November 21, 2018 at 4:43:01 PM UTC-6, Markus Wageringel

Post by Markus Wageringel
Hi everyone.
I created a Sage wrapper for the C interface of FGb, which makes it easy
to call FGb from within Sage. The sources are available on Github [1] and
[1] https://github.com/mwageringel/fgb_sage
FGb is a C-library by J. C. FaugÚre for computing Gröbner bases and
supposedly it is one of the faster implementations that exist. It is
included with Maple [2]. FGb is closed source, but comes with a C interface
• The computations run in parallel. (This only seems to work for
computations over finite fields.)
• Elimination/block orders are supported.
• It runs on Linux and Mac. (There seem to be some issues, though. I could
not get FGb to work on my Ubuntu machine. It fails with an "Illegal
instruction" error.)
In my Sage interface, I implemented just two functions: computing Gröbner
bases and elimination ideals. Supposedly, the FGb C-library supports other
functionality like computing Hilbert polynomials, but that part of the
library is not documented very well, so it does not make sense to try to
create wrappers for that. The focus is finding a Gröbner basis which, once
computed, can be used by Sage for further computations.
I just wanted to share this. Maybe it is useful for someone.
Markus
[2] https://www-polsys.lip6.fr/~jcf/FGb/Maple/index.html

[Dima Pasechnik]

Post by john_perry_usm
I walk into this discussion with some hesitancy, but Christian Eder has
developed a rather efficient F4 algorithm. [1] I know it works and is quite
fast, though I haven't compared it to the implementations mentioned above.
Unfortunately, I haven't heard from him in a while after he went off to
Iran for a few weeks, and he doesn't seem to have updated his site since
then, either.

https://github.com/ederc/ederc.github.io
was updated 5 days ago, so he must be just busy...

Post by john_perry_usm
Is integrating Eder's project something a group might be interested in
doing at [2]? I had planned to apply to work on integrating a similar
project at [2] (a different sort of F4-style Gröbner basis algorithm [3,4])
but perhaps [1] would be a good bet since there's no doubt about it and
Eder spent at least a year in Paris working with FaugÚre.
regards
john perry
[1] https://github.com/ederc/gb
[2] https://www.ima.umn.edu/2018-2019/SW7.22-26.19
[3] https://github.com/johnperry-math/DynGB
[4] https://dl.acm.org/citation.cfm?id=3087643
On Wednesday, November 21, 2018 at 4:43:01 PM UTC-6, Markus Wageringel

Post by Markus Wageringel
Hi everyone.
I created a Sage wrapper for the C interface of FGb, which makes it easy
to call FGb from within Sage. The sources are available on Github [1] and
[1] https://github.com/mwageringel/fgb_sage
FGb is a C-library by J. C. FaugÚre for computing Gröbner bases and
supposedly it is one of the faster implementations that exist. It is
included with Maple [2]. FGb is closed source, but comes with a C interface
• The computations run in parallel. (This only seems to work for
computations over finite fields.)
• Elimination/block orders are supported.
• It runs on Linux and Mac. (There seem to be some issues, though. I
could not get FGb to work on my Ubuntu machine. It fails with an "Illegal
instruction" error.)
In my Sage interface, I implemented just two functions: computing Gröbner
bases and elimination ideals. Supposedly, the FGb C-library supports other
functionality like computing Hilbert polynomials, but that part of the
library is not documented very well, so it does not make sense to try to
create wrappers for that. The focus is finding a Gröbner basis which, once
computed, can be used by Sage for further computations.
I just wanted to share this. Maybe it is useful for someone.
Markus
[2] https://www-polsys.lip6.fr/~jcf/FGb/Maple/index.html
--

You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

['Bill Hart' via sage-devel]

Post by john_perry_usm
I walk into this discussion with some hesitancy, but Christian Eder has
developed a rather efficient F4 algorithm. [1] I know it works and is quite
fast, though I haven't compared it to the implementations mentioned above.
Unfortunately, I haven't heard from him in a while after he went off to
Iran for a few weeks, and he doesn't seem to have updated his site since
then, either.

I assure you he is quite alive. I saw him a few minutes ago!

From his recent talks, his implementation is nowadays more than competitive.

[parisse]

Post by 'Bill Hart' via sage-devel
From his recent talks, his implementation is nowadays more than competitive.

I confirm that his timings are very good: for example almost 3 times faster
than Giac for cyclic9 modular. On the other hand, the implementation seems
not as complete: a quick look indicates that monomial ordering supported
are revlex and lex (no elimination, this is probably not hard to add), and
coefficients must belong to Z/pZ (support for Q would require more work...)

[Simon King]

Hi!

Post by parisse
not as complete: a quick look indicates that monomial ordering supported
are revlex and lex (no elimination, this is probably not hard to add), and
coefficients must belong to Z/pZ (support for Q would require more work...)

What is your definition of "elimination order"? If I understand
correctly, lex *is* an elimination order.

Best regards,
Simon

[parisse]

I meant a more efficient elimination order like double revlex.

Post by Simon King
Hi!
What is your definition of "elimination order"? If I understand
correctly, lex *is* an elimination order.
Best regards,
Simon

[Simon King]

Hi Bernard,

Post by parisse
I meant a more efficient elimination order like double revlex.

Actually I've never heard of that. The only reference I could find with
duckduckgo was the phrase
"Fast Gröbner basis f4 algorithm (revlex order and double
revlex for elimination), fast rational univariate
representation."
from the slides of your talk entitled "Giac/Xcas short presentation
Interactions with PARI/GP" held in January 2016.

Is it simply a block order where both blocks are revlex? If that's not
the case: Could you point me to an article where "double revlex" is
actually defined and where the benefits are pointed out?

Best regards,
Simon

[parisse]

Post by Simon King
Hi Bernard,

Post by parisse
I meant a more efficient elimination order like double revlex.

Actually I've never heard of that. The only reference I could find with
duckduckgo was the phrase
"Fast Gröbner basis f4 algorithm (revlex order and double
revlex for elimination), fast rational univariate
representation."
from the slides of your talk entitled "Giac/Xcas short presentation
Interactions with PARI/GP" held in January 2016.
Is it simply a block order where both blocks are revlex? If that's not
the case: Could you point me to an article where "double revlex" is
actually defined and where the benefits are pointed out?

Yes, it's exactly that, an efficient order for eliminate. In fact, I don't
know exactly what orders are supported in gb, I just guess from f4.c:
...
printf("field characteristic %11d\n", fc);
if (mo == 0) {
printf("monomial order DRL\n");
}
if (mo == 1) {
printf("monomial order LEX\n");
}
if ((mo != 0) && (mo != 1)) {
printf("monomial order DONT KNOW\n");
}
printf("linear algebra option %11d\n", laopt);
....

[john_perry_usm]

I've been back in touch with Christian Eder (thanks for assuring me he's
alive, Bill :-)) and he's happy to support an attempt to get the code into
Sage. He's working on extending the code to other fields & the like.

I will definitely apply for the afore-mentioned coding spring, to add at
least this system to Sage, maybe the other code I mentioned, too. If anyone
else is interested in this, I would be happy to have collaborators; just
email me privately, I guess? Again, the page is here [1].

john perry

[1] https://www.ima.umn.edu/2018-2019/SW7.22-26.19

On Wednesday, November 21, 2018 at 4:43:01 PM UTC-6, Markus Wageringel

Post by Markus Wageringel
Hi everyone.
I created a Sage wrapper for the C interface of FGb, which makes it easy
to call FGb from within Sage. The sources are available on Github [1] and
[1] https://github.com/mwageringel/fgb_sage
FGb is a C-library by J. C. FaugÚre for computing Gröbner bases and
supposedly it is one of the faster implementations that exist. It is
included with Maple [2]. FGb is closed source, but comes with a C interface
• The computations run in parallel. (This only seems to work for
computations over finite fields.)
• Elimination/block orders are supported.
• It runs on Linux and Mac. (There seem to be some issues, though. I could
not get FGb to work on my Ubuntu machine. It fails with an "Illegal
instruction" error.)
In my Sage interface, I implemented just two functions: computing Gröbner
bases and elimination ideals. Supposedly, the FGb C-library supports other
functionality like computing Hilbert polynomials, but that part of the
library is not documented very well, so it does not make sense to try to
create wrappers for that. The focus is finding a Gröbner basis which, once
computed, can be used by Sage for further computations.
I just wanted to share this. Maybe it is useful for someone.
Markus
[2] https://www-polsys.lip6.fr/~jcf/FGb/Maple/index.html