Toy implementation of F5 algorithm

[sagetrac-TristanVaccon]

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

[sagetrac-TristanVaccon]

Branch: u/TristanVaccon/toy_F5

[sagetrac-git]

Commit: f3b676a

[sagetrac-git]

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

f3b676a

Move toy_F5 to sage/rings/polynomial

[sagetrac-git]

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

06fbece

Remove toy_F5 from sage/rings/polynomial/padics

[sagetrac-git]

Changed commit from f3b676a to 06fbece

[sagetrac-TristanVaccon]

Changed keywords from none to sd87

[sagetrac-git]

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

193eb9a

New version.

[sagetrac-git]

Changed commit from 06fbece to 193eb9a

[xcaruso]

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]

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)

[sagetrac-git]

Changed commit from 193eb9a to 34fb934

[sagetrac-git]

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

34fb934

Better introduction. Minor other improvements.

[sagetrac-git]

Changed commit from 34fb934 to 5af6ccf

[sagetrac-git]

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

5af6ccf

4 new items in the reference.

[sagetrac-TristanVaccon]

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]

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.

[sagetrac-git]

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

78f0d49

Minor revision of references.

[sagetrac-git]

Changed commit from 5af6ccf to 78f0d49

[sagetrac-TristanVaccon]

comment:14

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

[fchapoton]

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