Toy implementation of F5 algorithm

8a446006-e38c-4d8b-a73b-1822fac50135 commented 7 years ago

This ticket implements Faugère's F5 algorithm.

CC: @xcaruso

Component: commutative algebra

Keywords: sd87

Author: Tristan Vaccon

Branch/Commit: u/TristanVaccon/toy_F5 @ 78f0d49

Issue created by migration from https://trac.sagemath.org/ticket/23461

8a446006-e38c-4d8b-a73b-1822fac50135 commented 7 years ago

Branch: u/TristanVaccon/toy_F5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Commit: f3b676a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

f3b676a Move toy_F5 to sage/rings/polynomial

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

06fbece Remove toy_F5 from sage/rings/polynomial/padics

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from f3b676a to 06fbece

8a446006-e38c-4d8b-a73b-1822fac50135 commented 7 years ago

Changed keywords from none to sd87

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

193eb9a New version.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 06fbece to 193eb9a

xcaruso commented 7 years ago

comment:7

According to me, your file could be much more educational that it is currently. Maybe, you should explain more basic concepts and ideas (such as signatures), explain notations and add more comments within your code. Another thing you could do is to detail (in the first doctest) step by step the execution of the F5 algorithm on a working simple example.

Other small comments:

why are you writing paires (and not pairs)?
in the doctest we should encapsulate your LaTeX formulae using backquotes (and not dollars)

fchapoton commented 7 years ago

comment:8

the symbol <> should not be used (not ok in python3), instead use !=
please remove the commented lines similar to #print "test", mon
because of the accents in Faugère and Gröbner, you need to add # -*- coding: utf-8 -*- as first line of the file
and the references should be moved to the master reference file (SAGE_ROOT/src/doc/en/reference/references/index.rst)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 193eb9a to 34fb934

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

34fb934 Better introduction. Minor other improvements.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 34fb934 to 5af6ccf

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

5af6ccf 4 new items in the reference.

8a446006-e38c-4d8b-a73b-1822fac50135 commented 7 years ago

comment:11

Thank you very much for your comments and suggestions!

I have made the corresponding corrections. I have also added more material to the Introduction with a complete small (minimal ?) example. I have not showed the matrices in this example though. I think it is better to leave this to the doctest of the functions dedicated to the linear algebra part of F5.

fchapoton commented 7 years ago

comment:12

in this line of the reference file:

+.. [VY2017] T. Vaccon, K.Yokoyama, *A Tropical F5 Algorithm*,

you need to add a \ (for obscure technical reasons..) as follows

+.. [VY2017] \T. Vaccon, K.Yokoyama, *A Tropical F5 Algorithm*,

when citing a reference, there must be an underscore after the brackets, for example

+We have followed [Fau02]_, [AP11]_, [EF17]_ and [VY17]_.

The following

+REFERENCES:
+
+.. [F02] Jean-Charles Faugère. *A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)*.  In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, ISSAC '02, pages 75-83, New York, NY, USA, 2002. ACM. 
+.. [AP11] Alberto Arri and John Perry. *The F5 criterion revised*.  In Journal of Symbolic Computation, 2011. Corrigendum in 2017.
+.. [EF17] Christian Eder and Jean-Charles Faugère. *A survey on signature-based algorithms for computing Gröbner bases*.  In Journal of Symbolic Computation, 2017.
+.. [VY17] T. Vaccon, K.Yokoyama, A Tropical F5 Algorithm, proceedings of ISSAC 2017.

should now be replaced by

+REFERENCES:
+
+- [F02]_ 
+- [AP11]_ 
+- [EF17]_
+- [VY17]_

You should try to respect the limitation that most lines are no longer than 80 columns. This means breaking all the long documentation lines.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

78f0d49 Minor revision of references.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 5af6ccf to 78f0d49

8a446006-e38c-4d8b-a73b-1822fac50135 commented 7 years ago

comment:14

Thank you very much for the comment. I have tried to update accordingly.

fchapoton commented 7 years ago

comment:15

same thing here (replace by - [VY17]_)

+    REFERENCES:
+
+    .. [VY17] T. Vaccon, K.Yokoyama, A Tropical F5 Algorithm, proceedings of ISSAC 2017.

And here (and almost everywhere !), there should be no empty line at the start of a documentation

+    r"""
+    
+    In the list of polynomials with signature G, remove the polynomials

sagemath / sage

Toy implementation of F5 algorithm #23461