Opened 6 years ago
Last modified 9 months ago
#18749 needs_info enhancement
Groebner basis computations with openf4 package
Reported by:  tcoladon  Owned by:  

Priority:  major  Milestone:  sagewishlist 
Component:  packages: optional  Keywords:  F4, groebner basis, ideal, sd87 
Cc:  ncohen, SimonKing, jpflori, zimmerma  Merged in:  
Authors:  Titouan Coladon  Reviewers:  Martin Albrecht, Travis Scrimshaw, Jeroen Demeyer, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  default algorithm choice 
Branch:  u/jdemeyer/f4 (Commits, GitHub, GitLab)  Commit:  0da1853a76d06188a2cd6f608c6b3df406259cea 
Dependencies:  Stopgaps: 
Description (last modified by )
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/openf41.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.
Change History (88)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
 Description modified (diff)
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 Sagedevel). 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.
comment:3 Changed 6 years ago by
 Cc ncohen added
comment:4 Changed 6 years ago by
I think they've put adding it as a standard package to a vote here: https://groups.google.com/forum/#!topic/sagedevel/CfZ8kzT8B2s
comment:5 Changed 6 years ago by
 Branch changed from u/tcoladon/f4 to u/malb/t18749_f4
 Commit changed from a2e200283801b3ad9c65542e598ba751663c5c4f to 75f896ac8673a5d0f8105aba9d287260327ed4c3
 f4 is rather generic for a software project implementing the F4 algorithm. If possible, it would be good to rename it (I know this is rather invasive). If you agree to rename this would affect the tarball, the file in the Sage library and the name of the algorithm when calling groebner_basis().
 I think the pyx file should be moved to
sage.libs.<libraryname>.<libraryname>.pyx
 I improved conversion a bit:
# before sage: P = PolynomialRing(GF(next_prime(2^31)), 8, 'x') sage: I = sage.rings.ideal.Cyclic(P) sage: from sage.rings.polynomial.groebner_basis_f4 import groebner_basis_f4 sage: %time gb0 = groebner_basis_f4(I) 6.4465777874 # < conversion time CPU times: user 14.8 s, sys: 400 ms, total: 15.2 s Wall time: 15.2 s # after sage: P = PolynomialRing(GF(next_prime(2^31)), 8, 'x') sage: I = sage.rings.ideal.Cyclic(P) sage: %time gb0 = groebner_basis_f4(I) 3.16141104698 # < conversion time CPU times: user 11.8 s, sys: 144 ms, total: 12 s Wall time: 11.9 s
 I cleaned the module up a bit under u/malb/t18749_f4
Last 10 new commits:
013879b  fix doctests & documentation

bfbb119  obey line width

676b798  rename modulo → modulus & raise error instead of printing to stddout

b324306  test exception

75f8302  specialised conversion from F4 string representation

0c76dbb  delete trailing whitespaces

10d8af5  return converted basis not strings

24e2191  Sageify interface to F4 more

48cf3c4  mark more doctests optional  f4

75f896a  fix prot interface for F4

comment:6 Changed 6 years ago by
 Commit changed from 75f896ac8673a5d0f8105aba9d287260327ed4c3 to ec6625b4001f57cdeed4ce9ab56c421c07e75666
Branch pushed to git repo; I updated commit sha1. New commits:
ec6625b  don't print SAGE_INC during compilation

comment:7 Changed 6 years ago by
The C++ code looks decent. Are you one of the upstream authors?
I didn't see a public source repo or bug tracker. If you don't want to host it yourself there is always github or bitbucket. But just putting a tarball on your homepage hasn't been best practice since the 90s ;)
Are the headers installed to $prefix/include/f4/include/f4.h? Why the extra /include/?
comment:8 Changed 6 years ago by
SPKG.txt says that openmp
is a dependency. But this is not mentioned above...
comment:9 Changed 6 years ago by
 Cc SimonKing added
comment:10 Changed 6 years ago by
 Commit changed from ec6625b4001f57cdeed4ce9ab56c421c07e75666 to cf1952a78d21e5778ca358dff120166d184a86c4
comment:11 in reply to: ↑ description Changed 6 years ago by
Replying to tcoladon:
Place the f4 archive in the upstream directory, then use sage sh sagefixpkgchecksums
This shouldn't be needed. The branch should contain the correct checksum!
comment:12 Changed 6 years ago by
It seems that the branch makes src/sage/rings/polynomial/multi_polynomial_ideal.py
executable??
comment:13 Changed 6 years ago by
At the same time, the files spkginstall
and spkgcheck
should be executable.
comment:14 Changed 6 years ago by
sage.rings.polynomial.groebner_basis_f4
should be an OptionalExtension
.
comment:15 Changed 6 years ago by
I played around with this ticket some more. On a Intel(R) Xeon(R) CPU E52667 v2 @ 3.30GHz with 16 real cores:
sage: P = PolynomialRing(GF(previous_prime(2^31)), 9, 'x') sage: I = sage.rings.ideal.Cyclic(P) sage: %time gb = I.groebner_basis('magma') CPU times: user 19.1 s, sys: 904 ms, total: 20 s Wall time: 5h 22min 33s sage: I = sage.rings.ideal.Cyclic(P) # avoid caching sage: %time gb16 = I.groebner_basis('f4', threads=16) CPU times: user 1h 23min 13s, sys: 33.6 s, total: 1h 23min 47s Wall time: 9min 54s sage: gb == gb16 True sage: %time gb8 = I.groebner_basis('f4', threads=8) CPU times: user 1h 4min 55s, sys: 27.9 s, total: 1h 5min 23s Wall time: 12min 23s sage: gb == gb8 True sage: %time gb1 = I.groebner_basis('f4', threads=1) CPU times: user 50min 26s, sys: 26.6 s, total: 50min 52s Wall time: 50min 56s sage: gb1 == gb True
comment:16 Changed 6 years ago by
I've been waiting 10 years for this!
comment:17 followup: ↓ 20 Changed 6 years ago by
The results over GF(2^{8}) seem to be incorrect, though:
sage: sr = mq.SR(1,1,1,4,gf2=False) # smallest scale small scale AES sage: F,s = sr.polynomial_system() sage: %time gb = F.groebner_basis() CPU times: user 8 ms, sys: 0 ns, total: 8 ms Wall time: 6.76 ms sage: gb[0] k003^2 + (a^2 + a + 1)*k003 + (a^3 + a^2 + 1) sage: %time gbf4 = F.groebner_basis('f4') GROEBNER BASIS : (1) # this output should not be here > 0 ms CPU times: user 8 ms, sys: 0 ns, total: 8 ms Wall time: 10.9 ms sage: gbf4 == gb # the output disagrees False sage: %time gbm = F.groebner_basis('magma') # checking who Magma agrees with CPU times: user 68 ms, sys: 20 ms, total: 88 ms Wall time: 997 ms sage: gbm == gb True
comment:18 Changed 6 years ago by
I made a few benchmarks, compared to giac, *natively* (conversions to sage take a significative amount of time at least for f4), with 1 thread, using a prime of size 24 bits (giac can go up to 31 bits, add about 20% time). For cyclic8, giac is a little faster (11s. vs 12) For katsura12, f4 is faster (45s vs 69s) For cyclic9: giac does it in about 15 minutes with 700M of RAM, I stopped the computation of f4 after about the same time because the memory used was reaching 23G (too much for my laptop). This is not specific to cyclic9, it also happens for katsura12.
comment:19 Changed 6 years ago by
I think that the time of conversion from F4 and giac to sage is quite similar. I also noticed that F4 is faster but the server I am working on has 16Go of ram and I had to interrupt the computation with F4 of cyclic9 mod prev_prime(2^{31). }
on sage with giac and giacpy the syntax is like this:
sage: P = PolynomialRing(GF(previous_prime(2^31)), 9, 'x') sage: I = sage.rings.ideal.Cyclic(P) sage: from giacpy import * sage: p=previous_prime(2^31) sage: time gb8B = (libgiac(I.gens()) % p).gbasis([P.gens()]) Time: CPU 1687.80 s, Wall: 1687.55 s sage: # the saved file is 84M sage: time gb8B.savegen('/home/han/cyclic9modp') Time: CPU 8.90 s, Wall: 8.92 s sage: #converting from giac to sage sage: time BG=Sequence(gb8B,P) Time: CPU 30.97 s, Wall: 30.97 s sage: time gb8Bbis=loadgiacgen('/home/han/cyclic9modp') Time: CPU 7.89 s, Wall: 7.89 s
comment:20 in reply to: ↑ 17 Changed 6 years ago by
Replying to malb:
The results over GF(2^{8}) seem to be incorrect, though:
sage: sr = mq.SR(1,1,1,4,gf2=False) # smallest scale small scale AES sage: F,s = sr.polynomial_system() sage: %time gb = F.groebner_basis() CPU times: user 8 ms, sys: 0 ns, total: 8 ms Wall time: 6.76 ms sage: gb[0] k003^2 + (a^2 + a + 1)*k003 + (a^3 + a^2 + 1) sage: %time gbf4 = F.groebner_basis('f4') GROEBNER BASIS : (1) # this output should not be here > 0 ms CPU times: user 8 ms, sys: 0 ns, total: 8 ms Wall time: 10.9 ms sage: gbf4 == gb # the output disagrees False
It is not clear for me that why gbf4 == gb should be True. I have nevertheless:
sage: gbf4==gb,gbf4.is_groebner(), gb.is_groebner() (False, True, True)
comment:21 followup: ↓ 22 Changed 6 years ago by
Thank you for the bug report and the wrapper improvement.
I have found the bug (due to SSE).
Does the name f4lib openf4 may be a suitable ?
For the "extra /include": I place in $prefix/include only libf4.h and f4.h, the "real" sources are placed in the $prefix/include/f4 directory where the declarations are separed from the definitions.
I will set up a git soon with the fix.
Let me know if you have any other requirements.
comment:22 in reply to: ↑ 21 ; followup: ↓ 23 Changed 6 years ago by
Replying to tcoladon:
Does the name f4lib openf4 may be a suitable ?
I'd say anything which is a proper name should work. 'f4lib' doesn't really qualify by that criterion I'd say, but it's better than 'f4'; 'openf4' could do. It's really up to you, though.
For the "extra /include": I place in $prefix/include only libf4.h and f4.h, the "real" sources are placed in the $prefix/include/f4 directory where the declarations are separed from the definitions.
Why do you install the sources at all? As far as I can see you instantiate all templates in libf4.cpp
anyway, so is there a need to copy the whole source code in local/include
?
comment:23 in reply to: ↑ 22 Changed 6 years ago by
Replying to malb:
Replying to tcoladon:
Does the name f4lib openf4 may be a suitable ?
I'd say anything which is a proper name should work. 'f4lib' doesn't really qualify by that criterion I'd say, but it's better than 'f4'; 'openf4' could do. It's really up to you, though.
For the "extra /include": I place in $prefix/include only libf4.h and f4.h, the "real" sources are placed in the $prefix/include/f4 directory where the declarations are separed from the definitions.
Why do you install the sources at all? As far as I can see you instantiate all templates in
libf4.cpp
anyway, so is there a need to copy the whole source code inlocal/include
?
Well, would you prefer a broken installation, that cannot be used at sage sh
prompt?
comment:24 Changed 6 years ago by
Why would that be a broken installation? The library is  as far as I can see  perfectly usable without dropping all .inl
files in local/include/f4/src
.
comment:25 Changed 6 years ago by
 Is there an "upstream" page? It should be mentioned in
SPKG.txt
.
 Is this right?
== License == * GNU GPLv3
It would be much better if it was under GPL version 3 or later. If this isn't the case, you should ask upstream if they are willing to release under GPL version 3 or later.
 Obviously, this shouldn't be there:
Put a bulleted list of dependencies here:
 In
module_list.py
, this shouldn't be neededdepends = [SAGE_INC + "/libf4.h"]
since you're explicitly refering to libf4.h
in the .pyx
file.
 For the copyright statement in
groebner_basis_f4.pyx
, please follow the format at
http://doc.sagemath.org/html/en/developer/coding_basics.html#headingsofsagelibrarycodefiles
 When you're done, remove
# commented out code
, in particular this funny thing:#include <Python.h>
 Format
INPUT
blocks like http://doc.sagemath.org/html/en/developer/coding_basics.html#thedocstringofafunctioncontent
comment:26 followup: ↓ 27 Changed 6 years ago by
I update the code on https://github.com/nauotit/openf4 (the bug is fixed)
and the Sage files in the branch u/tcoladon/f4.
The new upstream name is openf4.
I don't understand your question about the licence?
If the sources installation is a problem, we can remove them (just change the Makefile.am in the src directory) in a special target dedicated to Sage?
I haven't deleted the # lines in file groebner_basis_f4.pyx in case Givaro version is updated.
For the comparison with Magma, I'm not sure that openf4 is better on smaller prime fields. Magma is very slow when the characteristic is higher than 2^{24 }
comment:27 in reply to: ↑ 26 Changed 6 years ago by
Replying to tcoladon:
I don't understand your question about the licence?
There is a difference between releasing between releasing a project under "GPL version 3" and "GPL version 3 or any later version". The latter is much preferred in case a GPL version 4 ever comes out and we want to be compatible with that.
comment:28 Changed 6 years ago by
Thank you, the upstream is under GPLv3 or any later version, I have updated the SPKG.txt.
comment:29 Changed 6 years ago by
Which tarball do the hashes in checksums.ini refer to?
comment:30 Changed 6 years ago by
I have updated http://nauotit.github.io/openf4/ with the checksums.ini refered tarball.
comment:31 Changed 6 years ago by
 Commit changed from cf1952a78d21e5778ca358dff120166d184a86c4 to 2d15c6a5fc0ba8590f1c8fbc7d0f09362bb2246f
Branch pushed to git repo; I updated commit sha1. New commits:
cfbb262  Format Sage files and change upstream name: f4 > openf4

57361bd  Change licence from GNU GPLv3 to GPL version 3 or any later version

a15018a  Merge branch 'u/tcoladon/f4' of trac.sagemath.org:sage into u/tcoladon/f4

dee79b4  Merge branch 'u/tcoladon/f4' into f4

2d15c6a  Merge branch 'u/tcoladon/f4' into f4

comment:32 Changed 6 years ago by
 Commit changed from 2d15c6a5fc0ba8590f1c8fbc7d0f09362bb2246f to cc7aa9ff808acce533ef4f23799a0aa0eb548759
Branch pushed to git repo; I updated commit sha1. New commits:
1f51227  mark OpenMP as optional dependency in SPKG.txt

c8d4b94  make executable files executable

5796942  drop executable bit from multi_polynomial_ideal.py

e214336  openf4 inteface is optional

6c82642  move groebner_basis_f4 to openf4 and fix doctests

1240e77  update copyright statement to Sage standard

cc7aa9f  docstring & indentation clean up

comment:33 followup: ↓ 37 Changed 6 years ago by
I should have addressed all issues raised on this ticket with respect to the Sage interface. As far as I can see, what remains to be done is to clean up Makefile.am to normalise what is installed where? Anything I overlooked?
comment:34 Changed 6 years ago by
 Commit changed from cc7aa9ff808acce533ef4f23799a0aa0eb548759 to 33fbbfa9edbb9e7d2b5dc9dc15cf4074318ea894
Branch pushed to git repo; I updated commit sha1. New commits:
33fbbfa  only import openf4 if requested

comment:35 Changed 6 years ago by
 Commit changed from 33fbbfa9edbb9e7d2b5dc9dc15cf4074318ea894 to 252ddd1e1e1544126d46e0d553886343594afcf6
Branch pushed to git repo; I updated commit sha1. New commits:
252ddd1  mark more openf4 doctests optional

comment:36 Changed 6 years ago by
 Commit changed from 252ddd1e1e1544126d46e0d553886343594afcf6 to b14d81e10aac61115e3f77019c032aee273d09bd
Branch pushed to git repo; I updated commit sha1. New commits:
b14d81e  add another optional flag for openf4

comment:37 in reply to: ↑ 33 Changed 6 years ago by
Replying to malb:
Anything I overlooked?
It looks pretty good indeed.
I just noticed this Cython warning:
warning: sage/libs/openf4.pyx:135:29: Unreachable code
Don't forget to set the ticket to needs_review when you really want this to be reviewed.
comment:38 Changed 6 years ago by
 Commit changed from b14d81e10aac61115e3f77019c032aee273d09bd to e388b7ef03812fb47c41737fa566ecc97ca89557
Branch pushed to git repo; I updated commit sha1. New commits:
e388b7e  comment out unreachable code

comment:39 Changed 6 years ago by
Thanks, fixed the unreachable code thing. I'm in no position to set the ticket to "needs review". I think upstream should be cleaned up first (but not everyone agrees) and I'm also not the primary author anyway, just lending a hand on the Sage side.
comment:40 Changed 6 years ago by
 Status changed from new to needs_info
comment:41 Changed 6 years ago by
The sources installation is indeed required. libopenf4.cpp includes ideal.h which needs some *.inl files. If everything else is OK, I can change the ticket to "need review"?
comment:42 Changed 6 years ago by
Fine by me.
comment:43 Changed 6 years ago by
 Status changed from needs_info to needs_review
comment:44 Changed 6 years ago by
 Cc jpflori added
comment:45 Changed 6 years ago by
why all this naming mess? Would it be easier to call the package f4, just as the tarball is called?
No, really, it's totally unneeded complexity that is added this way.
comment:46 followup: ↓ 47 Changed 6 years ago by
The tarball is not called f4, please read the comments above.
comment:47 in reply to: ↑ 46 Changed 6 years ago by
 Status changed from needs_review to needs_work
Replying to malb:
The tarball is not called f4, please read the comments above.
I read the ticket description. It tells you to get https://wwwfourier.ujfgrenoble.fr/~viva/f4/f41.0.0.tar.gz (or rather it doesn't really tell you this, it just gives you https://wwwfourier.ujfgrenoble.fr/~viva/f4/html/index.html)
When you set a ticket up for review, can you at least provide clear instructions on installing all the stuff needed?
comment:48 Changed 6 years ago by
 Cc zimmerma added
comment:49 Changed 6 years ago by
Agreed, the description should be upgraded.
comment:50 Changed 6 years ago by
Could you also add some words about the ram needed by one or two examples? (the first time I tried I had difficulties with too much swapping)
comment:51 Changed 6 years ago by
Hi Titouan, can you update the description of this ticket so people can review it?
comment:52 Changed 6 years ago by
 Description modified (diff)
comment:53 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:54 Changed 6 years ago by
 Status changed from needs_review to needs_work
Ticket description still does not give a link to the tarball to be used, or otherwise not say how exactly to create one. Running sage sh sagefixpkgchecksums
must be done by the package creator, and not by the testers.
Sorry, but really, how much work is to fix this? Please, please, fix this quickly....
comment:55 Changed 6 years ago by
The checksum in the branch idenitifies the tarball to be used by the package. I don't see how without this specified one can talk about testing and reviewing anything...
comment:56 Changed 6 years ago by
 Description modified (diff)
comment:57 Changed 6 years ago by
OK, that's better. Does one really need to do sage i c f openf4
? For me
sage i openf4
works just as well, and this is the way it must work, to be includeable into Sage.
comment:58 Changed 6 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:59 Changed 6 years ago by
 Status changed from needs_review to needs_work
Am I correct in thinking that C++ vector[string]
things there are allocated on the stack, and are automatically freed, so we don't need to worry about dealloc?
comment:60 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:61 Changed 6 years ago by
 Reviewers set to Martin Albrecht, Travis Scrimshaw, Jeroen Demeyer, Dima Pasechnik
comment:62 Changed 6 years ago by
sage: I Ideal (32567592*x^2  134376780*x  99453050, 102821173*x^2  133875255*x + 114754735) of Multivariate Polynomial Ring in x over Finite Field of size 273389687 sage: I.groebner_basis() [1] sage: I.groebner_basis('openf4') [x]
The openf4 output seems wrong.
comment:63 Changed 6 years ago by
another difference:
sage: P.<x1,x2,x3,x4,x5> = PolynomialRing(GF(143107493)) sage: I=ideal([7253051*x1^2 + 52764828*x1*x2  1593629*x2^2  30491382*x1*x4  15421743, 2778386*x1^2 + 46128944*x2^2  28328699*x2*x3 + 35619408*x1*x4  47336793*x4^2, 50713151*x1^2 + 33804903*x1*x3 + 4639379*x3*x4  29371044*x1  55622885*x4, 17812925*x1*x2  60567702*x3^2  17218643*x2*x4 + 15189711*x1 + 683651*x4, 42755489*x1*x3  60418193*x2*x4 + 56537689*x4^2  6152933*x3 + 53988116]) sage: I.groebner_basis() [1] sage: I.groebner_basis('openf4') [x1, x2, x3, x4]
comment:64 Changed 6 years ago by
 Status changed from positive_review to needs_work
comment:65 Changed 6 years ago by
a simpler example in 3 variables where I.groebner_basis()
and I.groebner_basis('openf4')
disagree:
Ideal (381588408*x0^2 + 476686997*x2^2  462809584*x0 + 257786256*x2  114361905, 165319008*x0^2 + 74443335*x0*x2  139862633*x2^2  274498434*x0 + 48302322, 462665673*x0^2 + 458273559*x2^2  602419172*x0 + 103972832*x2  383910315) of Multivariate Polynomial Ring in x0, x1, x2 over Finite Field of size 1217734367 [1] [x0, x2]
comment:66 Changed 6 years ago by
also:
sage: P = PolynomialRing(GF(2), 1, 'x') sage: I = ideal([P(0)]) sage: I.groebner_basis('openf4') ... SignalError: Segmentation fault
comment:67 followups: ↓ 68 ↓ 76 Changed 6 years ago by
Thank you for the bug reports. They are solved. I have updated the tarball http://nauotit.github.io/openf4/openf41.0.0.tar.gz and the corresponding checksums.ini on the branch u/tcoladon/f4.
comment:68 in reply to: ↑ 67 Changed 6 years ago by
 Branch changed from u/malb/t18749_f4 to u/tcoladon/f4
 Commit changed from e388b7ef03812fb47c41737fa566ecc97ca89557 to ae15d4bbf92b91c121bdb488cdbf9d54120574cf
Replying to tcoladon:
Thank you for the bug reports. They are solved. I have updated the tarball http://nauotit.github.io/openf4/openf41.0.0.tar.gz and the corresponding checksums.ini on the branch u/tcoladon/f4.
New commits:
ae15d4b  Update checksum of the new tarball: solve bug of comments 62,63,65 and 66

comment:69 Changed 6 years ago by
As far as I can see, examples from comments 62,63,65 and 66 were not added to the doctests. Can you do this, so that it can be checked automatically?
comment:70 Changed 6 years ago by
Also, the current branch ignores all my fixes from u/malb/t18749_f4
comment:71 Changed 6 years ago by
 Commit changed from ae15d4bbf92b91c121bdb488cdbf9d54120574cf to 5784aeebf1654c194f4dc9333c221b9856eeb585
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
5796942  drop executable bit from multi_polynomial_ideal.py

e214336  openf4 inteface is optional

6c82642  move groebner_basis_f4 to openf4 and fix doctests

1240e77  update copyright statement to Sage standard

cc7aa9f  docstring & indentation clean up

33fbbfa  only import openf4 if requested

252ddd1  mark more openf4 doctests optional

b14d81e  add another optional flag for openf4

e388b7e  comment out unreachable code

5784aee  Merge branch 'u/malb/t18749_f4' of git://trac.sagemath.org/sage into u/tcoladon/f4

comment:72 Changed 6 years ago by
The doctests are added: checktrivial164bits.cpp <> comment 62 checktrivial264bits.cpp <> comment 65 checktrivial364bits.cpp <> comment 63 checktrivial564bits.cpp <> comment 66
We can stay on u/malb/t18749_f4 if it is easier ? I merge u/malb/t18749_f4 into u/tcoladon/f4, in order to add all the fixes.
comment:73 Changed 6 years ago by
 Merging my branch into yours is fine.
 Doctests refers to tests added to Sage in the documentation for a function. It might be good to add those tests there as well.
comment:74 Changed 6 years ago by
 Commit changed from 5784aeebf1654c194f4dc9333c221b9856eeb585 to b584ac72ab932647745e135d18c5bafecef72cb3
Branch pushed to git repo; I updated commit sha1. New commits:
b584ac7  Add #optional openf4 to doctest

comment:75 Changed 6 years ago by
I have added examples to the doctest.
However since I merge the branch u/malb/t18749_f4 into u/malb/t18749_f4, I have a problem with some unrelated files:
When I run ./sage br, I get a lot of "Error compiling Cython file:" whose the first is:
Cythonizing sage/categories/map.pyx Error compiling Cython file: from cpython.object cimport Py_TYPE, PyTypeObject?
comment:76 in reply to: ↑ 67 Changed 6 years ago by
Replying to tcoladon:
I have updated the tarball http://nauotit.github.io/openf4/openf41.0.0.tar.gz
thanks. It would be good to use different numbers for different versions (1.0.0 was already used before, see comment 47).
comment:77 Changed 5 years ago by
 Branch changed from u/tcoladon/f4 to u/jdemeyer/f4
comment:78 Changed 5 years ago by
 Commit changed from b584ac72ab932647745e135d18c5bafecef72cb3 to be9d96b9e364d701508074957a1c1d2609c7ad82
 Status changed from needs_work to needs_review
comment:79 Changed 5 years ago by
 Commit changed from be9d96b9e364d701508074957a1c1d2609c7ad82 to aaef33b69986b1c27f68eb8a8cde6ee0d2561c25
Branch pushed to git repo; I updated commit sha1. New commits:
aaef33b  Minor fixes to exceptions

comment:80 Changed 5 years ago by
 Description modified (diff)
 Summary changed from Groebner basis computations with the F4 algorithm to Groebner basis computations with openf4 package
comment:81 in reply to: ↑ description ; followup: ↓ 83 Changed 5 years ago by
Replying to tcoladon:
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.
Is this acceptable? Why are strings used for the conversion? Can't we access the C data structures?
comment:82 Changed 5 years ago by
 Commit changed from aaef33b69986b1c27f68eb8a8cde6ee0d2561c25 to 0da1853a76d06188a2cd6f608c6b3df406259cea
Branch pushed to git repo; I updated commit sha1. New commits:
0da1853  Add .pxd file

comment:83 in reply to: ↑ 81 Changed 5 years ago by
Replying to jdemeyer:
Replying to tcoladon:
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.
Is this acceptable? Why are strings used for the conversion? Can't we access the C data structures?
I don't see any easy way to do this after quickly browsing openf4
source code.
As far as initialization is concerned, the only constructor for polynomials on top of move and copy contructors takes a vector of strings. You can init an empty polynomial and add terms one at a time but you have to sort the temrs first.
And to extract the result you have to do the same thing.
So my opinion is that such functions should be added to openf4, not the the sage wrapper. They could for example eat and spit vectors of Element.
comment:84 Changed 5 years ago by
 Milestone changed from sage6.8 to sage7.0
 Status changed from needs_review to needs_work
 Work issues set to default algorithm choice
Another thing: if openf4
is so much faster like you claim, it should be the default algorithm for Gröbner basis computations over rings which openf4
can handle. That would also greatly increase the testing coverage.
comment:85 followup: ↓ 86 Changed 5 years ago by
If the default choice is reconsidered, then I would recommend to run benchmarks in comparison with singular and giac. My own tests shows that for Z/pZ, giac is faster than openf4 and requires much less memory (e.g. less than 600M vs more than 20G for cyclic9). singular remains faster for very sparse problems where f4 is not appropriate. Cf. http://www.cecm.sfu.ca/~rpearcea/mgb.html
comment:86 in reply to: ↑ 85 Changed 5 years ago by
Replying to parisse:
If the default choice is reconsidered, then I would recommend to run benchmarks in comparison with singular and giac. My own tests shows that for Z/pZ, giac is faster than openf4 and requires much less memory (e.g. less than 600M vs more than 20G for cyclic9). singular remains faster for very sparse problems where f4 is not appropriate. Cf. http://www.cecm.sfu.ca/~rpearcea/mgb.html
I think that you are talking of giac > 1.2.2. Note that I have not yet updated the spkg (giac 1.2.0.19) so it is a bit slower than openf4 for cyclic9, but ram usage are indeed very different (for cyclic9 over GF(101) top shows for giac 1.2.0 from sage around 1G but I saw top around 60Go with openf4 from sage.)
comment:87 Changed 4 years ago by
 Keywords sd87 added
comment:88 Changed 9 months ago by
 Milestone changed from sage7.0 to sagewishlist
 Status changed from needs_work to needs_info
Setting spkg proposals that have not seen recent activity to "sagewishlist".
This looks very interesting.
Can you clarify what you're trying to achieve with this ticket. Do you want your F4 code to be a standard or an optional package? Note that adding standard packages requires a vote on [sagedevel] and usually some time during which the package was an optional package.
Does your package have a name other than F4?
Also, do you have an idea why the performance of the wrapper is so poor?