#18749: Groebner basis computations with the F4 algorithm
-------------------------------------+-------------------------------------
Reporter: tcoladon | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: packages: | Resolution:
optional | Merged in:
Keywords: F4, groebner | Reviewers:
basis, ideal | Work issues:
Authors: Titouan Coladon | Commit:
Report Upstream: N/A | a2e200283801b3ad9c65542e598ba751663c5c4f
Branch: u/tcoladon/f4 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Old description:
> We propose a new C++ library to compute Groebner basis over finite fields
> with the F4 algorithm.
> This library works on prime fields of characteristic < 2^32
> and on binary field extensions of degree < 64.
>
> The source code and a documentation are available on
> https://www-fourier.ujf-grenoble.fr/~viva/f4/html/index.html
>
> The branch attached to this ticket contains a wrapper (Cython) for this
> library.
> Place the f4 archive in the upstream directory, then use
> sage -sh sage-fix-pkg-checksums
> sage -i -c -f f4
> before using this branch.
>
> Informations on the new package:
>
> -Speed (on my computer without vectorisation):
>
> cyclic 8, GF(251):
> sage : 45.7 s
> f4 : 30.8 s
>
> katsura 12, GF(251):
> sage : 12min 36s
> f4 : 3min 16s
>
> cyclic 8, GF(65521):
> sage : 58.4
> f4 : 25s
>
> katsura 12, GF(65521):
> sage : 15min 47s
> f4 : 2min 46s
>
> cyclic 8, GF(4294967291) :
> sage : does not work
> f4 : 55.5 s
>
> katsura 12, GF(4294967291) :
> sage : does not work
> f4 : 11min 50s
>
> Ideal in 8 variables over GF(2^15):
> sage : 60 s
> f4 : 10s
>
> Ideal in 8 variables over GF(2^31):
> sage : 58.1 s
> f4 : 15s
>
> Ideal in 8 variables over GF(2^63):
> sage : 1min 18s
> f4 : 30s
>
> Documentation:
>
> Available with the package (doxygen).
> And in the updated file multi_polynomial_ideal.py, function
> groebner_basis.
>
> Usability:
>
> Can be used in the same way than other algorithms.
> However only the grevlex order is available.
> Detailed in the file multi_polynomial_ideal.py, function groebner_basis.
>
> Absence of memory leaks:
>
> Tested with valgrind.
>
> Maintainable:
>
> When the Givaro version of Sage will be updated, the package could be
> build with this dependency in order to handle the prime fields of big
> characteristics.
>
> Portability:
>
> In order to be efficient our package can use the SSE2 and SSE4 extensions
> (vectorisation).
> This extensions are automatically detected at build time (configure).
> However, even without these optimisations our package is more efficient
> than the current implemented algorithms in Sage.
> The package was tested on:
> - Ubuntu 12.04 (64 bits)
> - Ubuntu 14.04 (64 bits)
> - Debian 8 (32 bits)
> - Arch Linux (64 bits)
> - Mac OS X Yosemite (64 bits)
>
> Reasonable build time, size, dependencies:
>
> If the build time is a problem, examples can be removed from the
> makefile.am.
> Size: 12Mo
> Dependencies: Givaro is an optional dependency but a recent version is
> required.
>
> Note:
>
> The proposed wrapper in Cython is not very efficient and may be improved:
> for instance, the computation of katsura 12 over GF(4294967291) takes
> only 2min 11s,
> and more than 9 min are spent in the cython wrapper to convert the result
> into sage polynomials.
New description:
We propose a new C++ library to compute Groebner basis over finite fields
with the F4 algorithm.
This library works on prime fields of characteristic < 2^32^
and on binary field extensions of degree < 64.
The source code and a documentation are available on
https://www-fourier.ujf-grenoble.fr/~viva/f4/html/index.html
The branch attached to this ticket contains a wrapper (Cython) for this
library.
Place the f4 archive in the upstream directory, then use
sage -sh sage-fix-pkg-checksums
sage -i -c -f f4
before using this branch.
Informations on the new package:
-Speed (on my computer without vectorisation):
cyclic 8, GF(251):
sage : 45.7 s
f4 : 30.8 s
katsura 12, GF(251):
sage : 12min 36s
f4 : 3min 16s
cyclic 8, GF(65521):
sage : 58.4
f4 : 25s
katsura 12, GF(65521):
sage : 15min 47s
f4 : 2min 46s
cyclic 8, GF(4294967291) :
sage : does not work
f4 : 55.5 s
katsura 12, GF(4294967291) :
sage : does not work
f4 : 11min 50s
Ideal in 8 variables over GF(2^15^):
sage : 60 s
f4 : 10s
Ideal in 8 variables over GF(2^31^):
sage : 58.1 s
f4 : 15s
Ideal in 8 variables over GF(2^63^):
sage : 1min 18s
f4 : 30s
Documentation:
Available with the package (doxygen).
And in the updated file multi_polynomial_ideal.py, function
groebner_basis.
Usability:
Can be used in the same way than other algorithms.
However only the grevlex order is available.
Detailed in the file multi_polynomial_ideal.py, function groebner_basis.
Absence of memory leaks:
Tested with valgrind.
Maintainable:
When the Givaro version of Sage will be updated, the package could be
build with this dependency in order to handle the prime fields of big
characteristics.
Portability:
In order to be efficient our package can use the SSE2 and SSE4 extensions
(vectorisation).
This extensions are automatically detected at build time (configure).
However, even without these optimisations our package is more efficient
than the current implemented algorithms in Sage.
The package was tested on:
- Ubuntu 12.04 (64 bits)
- Ubuntu 14.04 (64 bits)
- Debian 8 (32 bits)
- Arch Linux (64 bits)
- Mac OS X Yosemite (64 bits)
Reasonable build time, size, dependencies:
If the build time is a problem, examples can be removed from the
makefile.am.
Size: 12Mo
Dependencies: Givaro is an optional dependency but a recent version is
required.
Note:
The proposed wrapper in Cython is not very efficient and may be improved:
for instance, the computation of katsura 12 over GF(4294967291) takes only
2min 11s,
and more than 9 min are spent in the cython wrapper to convert the result
into sage polynomials.
--
Comment (by tscrim):
With the latest beta versions of Sage, you'll need to add a file `type`
which contains the word "optional" (as new Sage packages start as
optional, but if you want to make this standard, you can make a request on
Sage-devel). You also need to make in `module_list.pyx` an optional
extension.
I'm guessing the conversion has to do with taking the basis as a vector of
strings and you need to convert it to a better python type. You probably
want to do this in a cdef function and have the python level function just
do the final conversions. Conversions to strings is typically the slowest
way to do things. It might be best to have a python data structure in the
bindings file more closer to your internal data structures.
--
Ticket URL: <http://trac.sagemath.org/ticket/18749#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
