#18749: Groebner basis computations with openf4 package
-------------------------------------+-------------------------------------
Reporter: tcoladon | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: packages: | Resolution:
optional | Merged in:
Keywords: F4, groebner | Reviewers: Martin Albrecht,
basis, ideal | Travis Scrimshaw, Jeroen Demeyer,
Authors: Titouan Coladon | Dima Pasechnik
Report Upstream: N/A | Work issues:
Branch: u/jdemeyer/f4 | Commit:
Dependencies: | aaef33b69986b1c27f68eb8a8cde6ee0d2561c25
| Stopgaps:
-------------------------------------+-------------------------------------
Description changed by jdemeyer:
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
> http://nauotit.github.io/openf4/
>
> The tarball is available on
> http://nauotit.github.io/openf4/openf4-1.0.0.tar.gz
>
> The branch attached to this ticket contains a wrapper (Cython) for this
> library.
> Place the openf4 archive in the upstream directory, then use
> `sage -i openf4`
> 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
>
> Memory requirement:
>
> The memory needed by openf4 depends on:
> - the number of variables of the polynomial ring.
> - the (unknown) maximum monomial degree reached during the computation.
> - the (unknown) size of the considered matrices.
>
> Even if our matrices are smaller than the ones of Magma, on cyclic 9 they
> exceed 70000 x 70000, which requires already around 20 GB on 4 Bytes
> integers.
>
>
> 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
http://nauotit.github.io/openf4/
The tarball is available on
http://nauotit.github.io/openf4/openf4-1.0.0.tar.gz
The branch attached to this ticket contains a wrapper (Cython) for this
library.
Place the openf4 archive in the upstream directory, then use
`sage -i openf4`
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
Memory requirement:
The memory needed by openf4 depends on:
- the number of variables of the polynomial ring.
- the (unknown) maximum monomial degree reached during the computation.
- the (unknown) size of the considered matrices.
Even if our matrices are smaller than the ones of Magma, on cyclic 9 they
exceed 70000 x 70000, which requires already around 20 GB on 4 Bytes
integers.
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#comment:80>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
