Opened 2 years ago

Last modified 2 years ago

#23461 needs_work enhancement

Toy implementation of F5 algorithm

Reported by: TristanVaccon Owned by:
Priority: major Milestone: sage-8.1
Component: commutative algebra Keywords: sd87
Cc: caruso Merged in:
Authors: Tristan Vaccon Reviewers:
Report Upstream: N/A Work issues:
Branch: u/TristanVaccon/toy_F5 (Commits) Commit: 78f0d494690fb3f5fc45c2bf5b013a85c0bd8525
Dependencies: Stopgaps:

Description

This ticket implements Faugère's F5 algorithm.

Change History (15)

comment:1 Changed 2 years ago by TristanVaccon

  • Branch set to u/TristanVaccon/toy_F5

comment:2 Changed 2 years ago by git

  • Commit set to f3b676a872990ca24a346725f42efa335b71f1b7

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

f3b676aMove toy_F5 to sage/rings/polynomial

comment:3 Changed 2 years ago by git

  • Commit changed from f3b676a872990ca24a346725f42efa335b71f1b7 to 06fbece7a158382cc6e55b8dc125c0cc75a628d9

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

06fbeceRemove toy_F5 from sage/rings/polynomial/padics

comment:4 Changed 2 years ago by TristanVaccon

  • Keywords sd87 added

comment:5 Changed 2 years ago by git

  • Commit changed from 06fbece7a158382cc6e55b8dc125c0cc75a628d9 to 193eb9aed1c1c1f97b19e2bd7dcb981fb5d14936

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

193eb9aNew version.

comment:6 Changed 2 years ago by TristanVaccon

  • Status changed from new to needs_review

comment:7 Changed 2 years ago by caruso

  • Status changed from needs_review to needs_work

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)
Last edited 2 years ago by caruso (previous) (diff)

comment:8 Changed 2 years ago by chapoton

  • 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)
Last edited 2 years ago by chapoton (previous) (diff)

comment:9 Changed 2 years ago by git

  • Commit changed from 193eb9aed1c1c1f97b19e2bd7dcb981fb5d14936 to 34fb93418bbcf42da92df5132ba06626144de338

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

34fb934Better introduction. Minor other improvements.

comment:10 Changed 2 years ago by git

  • Commit changed from 34fb93418bbcf42da92df5132ba06626144de338 to 5af6ccfec6d2a1b8aeddc4d137c9e178d6f99d0d

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

5af6ccf4 new items in the reference.

comment:11 Changed 2 years ago by TristanVaccon

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.

comment:12 Changed 2 years ago by chapoton

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

comment:13 Changed 2 years ago by git

  • Commit changed from 5af6ccfec6d2a1b8aeddc4d137c9e178d6f99d0d to 78f0d494690fb3f5fc45c2bf5b013a85c0bd8525

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

78f0d49Minor revision of references.

comment:14 Changed 2 years ago by TristanVaccon

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

comment:15 Changed 2 years ago by chapoton

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
Note: See TracTickets for help on using tickets.