Opened 4 years ago

Last modified 21 months ago

#18749 needs_work enhancement

Groebner basis computations with openf4 package

Reported by: tcoladon Owned by:
Priority: major Milestone: sage-7.0
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) Commit: 0da1853a76d06188a2cd6f608c6b3df406259cea
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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 < 232 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(215): sage : 60 s f4 : 10s

Ideal in 8 variables over GF(231): sage : 58.1 s f4 : 15s

Ideal in 8 variables over GF(263): 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 (87)

comment:1 Changed 4 years ago by malb

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 [sage-devel] 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?

comment:2 Changed 4 years ago by tscrim

  • 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 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.

comment:3 Changed 4 years ago by ncohen

  • Cc ncohen added

comment:4 Changed 4 years ago by was

I think they've put adding it as a standard package to a vote here: https://groups.google.com/forum/#!topic/sage-devel/CfZ8kzT8B2s

comment:5 Changed 4 years ago by malb

  • 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:

013879bfix doctests & documentation
bfbb119obey line width
676b798rename modulo → modulus & raise error instead of printing to stddout
b324306test exception
75f8302specialised conversion from F4 string representation
0c76dbbdelete trailing whitespaces
10d8af5return converted basis not strings
24e2191Sage-ify interface to F4 more
48cf3c4mark more doctests optional - f4
75f896afix prot interface for F4

comment:6 Changed 4 years ago by git

  • Commit changed from 75f896ac8673a5d0f8105aba9d287260327ed4c3 to ec6625b4001f57cdeed4ce9ab56c421c07e75666

Branch pushed to git repo; I updated commit sha1. New commits:

ec6625bdon't print SAGE_INC during compilation

comment:7 Changed 4 years ago by vbraun

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 4 years ago by dimpase

SPKG.txt says that openmp is a dependency. But this is not mentioned above...

comment:9 Changed 4 years ago by SimonKing

  • Cc SimonKing added

comment:10 Changed 4 years ago by git

  • Commit changed from ec6625b4001f57cdeed4ce9ab56c421c07e75666 to cf1952a78d21e5778ca358dff120166d184a86c4

Branch pushed to git repo; I updated commit sha1. New commits:

bfca7d5Merge branch 'develop' into f4
cf1952aadd required type field for f4

comment:11 in reply to: ↑ description Changed 4 years ago by jdemeyer

Replying to tcoladon:

Place the f4 archive in the upstream directory, then use sage -sh sage-fix-pkg-checksums

This shouldn't be needed. The branch should contain the correct checksum!

comment:12 Changed 4 years ago by jdemeyer

It seems that the branch makes src/sage/rings/polynomial/multi_polynomial_ideal.py executable??

comment:13 Changed 4 years ago by jdemeyer

At the same time, the files spkg-install and spkg-check should be executable.

comment:14 Changed 4 years ago by jdemeyer

sage.rings.polynomial.groebner_basis_f4 should be an OptionalExtension.

comment:15 Changed 4 years ago by malb

I played around with this ticket some more. On a Intel(R) Xeon(R) CPU E5-2667 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 4 years ago by was

I've been waiting 10 years for this!

comment:17 follow-up: Changed 4 years ago by malb

The results over GF(28) 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

Last edited 4 years ago by malb (previous) (diff)

comment:18 Changed 4 years ago by parisse

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 4 years ago by frederichan

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(231).

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 4 years ago by frederichan

Replying to malb:

The results over GF(28) 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 follow-up: Changed 4 years ago by tcoladon

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 ; follow-up: Changed 4 years ago by 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 in local/include?

comment:23 in reply to: ↑ 22 Changed 4 years ago by dimpase

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 in local/include?

Well, would you prefer a broken installation, that cannot be used at sage -sh prompt?

comment:24 Changed 4 years ago by malb

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 4 years ago by jdemeyer

  1. Is there an "upstream" page? It should be mentioned in SPKG.txt.
  1. 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.

  1. Obviously, this shouldn't be there:
    Put a bulleted list of dependencies here:
    
  1. In module_list.py, this shouldn't be needed
    depends = [SAGE_INC + "/libf4.h"]
    

since you're explicitly refering to libf4.h in the .pyx file.

  1. For the copyright statement in groebner_basis_f4.pyx, please follow the format at

http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files

  1. When you're done, remove # commented out code, in particular this funny thing:
    #include <Python.h>
    
  1. Format INPUT blocks like http://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content

comment:26 follow-up: Changed 4 years ago by tcoladon

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 224

comment:27 in reply to: ↑ 26 Changed 4 years ago by jdemeyer

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 4 years ago by tcoladon

Thank you, the upstream is under GPLv3 or any later version, I have updated the SPKG.txt.

comment:29 Changed 4 years ago by malb

Which tarball do the hashes in checksums.ini refer to?

comment:30 Changed 4 years ago by tcoladon

I have updated http://nauotit.github.io/openf4/ with the checksums.ini refered tarball.

comment:31 Changed 4 years ago by git

  • Commit changed from cf1952a78d21e5778ca358dff120166d184a86c4 to 2d15c6a5fc0ba8590f1c8fbc7d0f09362bb2246f

Branch pushed to git repo; I updated commit sha1. New commits:

cfbb262Format Sage files and change upstream name: f4 -> openf4
57361bdChange licence from GNU GPLv3 to GPL version 3 or any later version
a15018aMerge branch 'u/tcoladon/f4' of trac.sagemath.org:sage into u/tcoladon/f4
dee79b4Merge branch 'u/tcoladon/f4' into f4
2d15c6aMerge branch 'u/tcoladon/f4' into f4

comment:32 Changed 4 years ago by git

  • Commit changed from 2d15c6a5fc0ba8590f1c8fbc7d0f09362bb2246f to cc7aa9ff808acce533ef4f23799a0aa0eb548759

Branch pushed to git repo; I updated commit sha1. New commits:

1f51227mark OpenMP as optional dependency in SPKG.txt
c8d4b94make executable files executable
5796942drop executable bit from multi_polynomial_ideal.py
e214336openf4 inteface is optional
6c82642move groebner_basis_f4 to openf4 and fix doctests
1240e77update copyright statement to Sage standard
cc7aa9fdocstring & indentation clean up

comment:33 follow-up: Changed 4 years ago by malb

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 4 years ago by git

  • Commit changed from cc7aa9ff808acce533ef4f23799a0aa0eb548759 to 33fbbfa9edbb9e7d2b5dc9dc15cf4074318ea894

Branch pushed to git repo; I updated commit sha1. New commits:

33fbbfaonly import openf4 if requested

comment:35 Changed 4 years ago by git

  • Commit changed from 33fbbfa9edbb9e7d2b5dc9dc15cf4074318ea894 to 252ddd1e1e1544126d46e0d553886343594afcf6

Branch pushed to git repo; I updated commit sha1. New commits:

252ddd1mark more openf4 doctests optional

comment:36 Changed 4 years ago by git

  • Commit changed from 252ddd1e1e1544126d46e0d553886343594afcf6 to b14d81e10aac61115e3f77019c032aee273d09bd

Branch pushed to git repo; I updated commit sha1. New commits:

b14d81eadd another optional flag for openf4

comment:37 in reply to: ↑ 33 Changed 4 years ago by jdemeyer

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 4 years ago by git

  • Commit changed from b14d81e10aac61115e3f77019c032aee273d09bd to e388b7ef03812fb47c41737fa566ecc97ca89557

Branch pushed to git repo; I updated commit sha1. New commits:

e388b7ecomment out unreachable code

comment:39 Changed 4 years ago by malb

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 4 years ago by malb

  • Status changed from new to needs_info

comment:41 Changed 4 years ago by tcoladon

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 4 years ago by malb

Fine by me.

comment:43 Changed 4 years ago by tcoladon

  • Status changed from needs_info to needs_review

comment:44 Changed 4 years ago by jpflori

  • Cc jpflori added

comment:45 Changed 4 years ago by dimpase

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.

Last edited 4 years ago by dimpase (previous) (diff)

comment:46 follow-up: Changed 4 years ago by malb

The tarball is not called f4, please read the comments above.

comment:47 in reply to: ↑ 46 Changed 4 years ago by dimpase

  • 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://www-fourier.ujf-grenoble.fr/~viva/f4/f4-1.0.0.tar.gz (or rather it doesn't really tell you this, it just gives you https://www-fourier.ujf-grenoble.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 4 years ago by zimmerma

  • Cc zimmerma added

comment:49 Changed 4 years ago by malb

Agreed, the description should be upgraded.

comment:50 Changed 4 years ago by frederichan

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 4 years ago by malb

Hi Titouan, can you update the description of this ticket so people can review it?

comment:52 Changed 4 years ago by tcoladon

  • Description modified (diff)

comment:53 Changed 4 years ago by malb

  • Status changed from needs_work to needs_review

comment:54 Changed 4 years ago by dimpase

  • 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 sage-fix-pkg-checksums 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 4 years ago by dimpase

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 4 years ago by tcoladon

  • Description modified (diff)

comment:57 Changed 4 years ago by dimpase

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 4 years ago by dimpase

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:59 Changed 4 years ago by dimpase

  • 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?

Last edited 4 years ago by dimpase (previous) (diff)

comment:60 Changed 4 years ago by dimpase

  • Status changed from needs_work to positive_review

comment:61 Changed 4 years ago by dimpase

  • Reviewers set to Martin Albrecht, Travis Scrimshaw, Jeroen Demeyer, Dima Pasechnik

comment:62 Changed 4 years ago by zimmerma

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 4 years ago by zimmerma

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 4 years ago by dimpase

  • Status changed from positive_review to needs_work

comment:65 Changed 4 years ago by zimmerma

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 4 years ago by zimmerma

also:

sage: P = PolynomialRing(GF(2), 1, 'x')
sage: I = ideal([P(0)])
sage: I.groebner_basis('openf4')
...
SignalError: Segmentation fault

comment:67 follow-ups: Changed 4 years ago by tcoladon

Thank you for the bug reports. They are solved. I have updated the tarball http://nauotit.github.io/openf4/openf4-1.0.0.tar.gz and the corresponding checksums.ini on the branch u/tcoladon/f4.

comment:68 in reply to: ↑ 67 Changed 4 years ago by dimpase

  • 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/openf4-1.0.0.tar.gz and the corresponding checksums.ini on the branch u/tcoladon/f4.


New commits:

ae15d4bUpdate checksum of the new tarball: solve bug of comments 62,63,65 and 66

comment:69 Changed 4 years ago by dimpase

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 4 years ago by malb

Also, the current branch ignores all my fixes from u/malb/t18749_f4

comment:71 Changed 4 years ago by git

  • Commit changed from ae15d4bbf92b91c121bdb488cdbf9d54120574cf to 5784aeebf1654c194f4dc9333c221b9856eeb585

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

5796942drop executable bit from multi_polynomial_ideal.py
e214336openf4 inteface is optional
6c82642move groebner_basis_f4 to openf4 and fix doctests
1240e77update copyright statement to Sage standard
cc7aa9fdocstring & indentation clean up
33fbbfaonly import openf4 if requested
252ddd1mark more openf4 doctests optional
b14d81eadd another optional flag for openf4
e388b7ecomment out unreachable code
5784aeeMerge branch 'u/malb/t18749_f4' of git://trac.sagemath.org/sage into u/tcoladon/f4

comment:72 Changed 4 years ago by tcoladon

The doctests are added: check-trivial1-64bits.cpp <-> comment 62 check-trivial2-64bits.cpp <-> comment 65 check-trivial3-64bits.cpp <-> comment 63 check-trivial5-64bits.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 4 years ago by malb

  • 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 4 years ago by git

  • Commit changed from 5784aeebf1654c194f4dc9333c221b9856eeb585 to b584ac72ab932647745e135d18c5bafecef72cb3

Branch pushed to git repo; I updated commit sha1. New commits:

b584ac7Add #optional openf4 to doctest

comment:75 Changed 4 years ago by tcoladon

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 4 years ago by zimmerma

Replying to tcoladon:

I have updated the tarball http://nauotit.github.io/openf4/openf4-1.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 3 years ago by jdemeyer

  • Branch changed from u/tcoladon/f4 to u/jdemeyer/f4

comment:78 Changed 3 years ago by jdemeyer

  • Commit changed from b584ac72ab932647745e135d18c5bafecef72cb3 to be9d96b9e364d701508074957a1c1d2609c7ad82
  • Status changed from needs_work to needs_review

Merged latest beta and added a few trivial fixes.


New commits:

a97048dMerge tag '7.0.beta3' into t/18749/f4
a37d63fSmall fixes to openf4 build
be9d96bReorganize doctests

comment:79 Changed 3 years ago by git

  • Commit changed from be9d96b9e364d701508074957a1c1d2609c7ad82 to aaef33b69986b1c27f68eb8a8cde6ee0d2561c25

Branch pushed to git repo; I updated commit sha1. New commits:

aaef33bMinor fixes to exceptions

comment:80 Changed 3 years ago by jdemeyer

  • 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 ; follow-up: Changed 3 years ago by 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?

comment:82 Changed 3 years ago by git

  • Commit changed from aaef33b69986b1c27f68eb8a8cde6ee0d2561c25 to 0da1853a76d06188a2cd6f608c6b3df406259cea

Branch pushed to git repo; I updated commit sha1. New commits:

0da1853Add .pxd file

comment:83 in reply to: ↑ 81 Changed 3 years ago by jpflori

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 3 years ago by jdemeyer

  • Milestone changed from sage-6.8 to sage-7.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 follow-up: Changed 3 years ago by 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

comment:86 in reply to: ↑ 85 Changed 3 years ago by frederichan

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 21 months ago by roed

  • Keywords sd87 added
Note: See TracTickets for help on using tickets.