#18749: Groebner basis computations with the F4 algorithm
-------------------------------------+-------------------------------------
Reporter: tcoladon | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: packages: optional | Keywords: F4, groebner
Merged in: | basis, ideal
Reviewers: | Authors: Titouan Coladon
Work issues: | Report Upstream: N/A
Commit: | Branch: u/tcoladon/f4
a2e200283801b3ad9c65542e598ba751663c5c4f| Dependencies:
Stopgaps: |
-------------------------------------+-------------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/18749>
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.
