Toy implementation of Matrix-F5 algorithm and various adaptation

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.47k stars 485 forks source link

Toy implementation of Matrix-F5 algorithm and various adaptation #20997

Open 8a446006-e38c-4d8b-a73b-1822fac50135 opened 8 years ago

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

This ticket provides a first toy implementation of the Matrix-F5 algorithm to compute Gröbner bases.

Many variants of this algorithm are available:

The classical one (see https://hal.inria.fr/hal-00974810).
An adaptation for more stable computation of p-adic Gröbner bases (see http://arxiv.org/abs/1403.5464).
Various adaptations to the computation of tropical Gröbner bases (see http://arxiv.org/abs/1402.6675).

Doctests are provided.

To implement the algorithms, we define a class of Macaulay matrices with extra information (signatures, labels, etc...).

CC: @defeo @simon-king-jena @saraedum @xcaruso

Component: padics

Keywords: Matrix-F5 algorithm, Gröbner bases, tropical Gröbner bases, p-adic computation

Author: Tristan Vaccon

Branch/Commit: public/ticket/20997 @ e9c2544

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

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

Toy implementation of the Matrix-F5 algorithm and many adaptations

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

comment:1

Attachment: toy_MatrixF5.py.gz

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

Description changed:

--- 
+++ 
@@ -6,3 +6,5 @@
 * Various adaptations to the computation of tropical Gröbner bases (see http://arxiv.org/abs/1402.6675).

 Doctests are provided.
+
+To implement the algorithms, we define a class of Macaulay matrices with extra information (signatures, labels, etc...).

fchapoton commented 8 years ago

comment:2

Hello, and welcome !

Could you provide a git branch for your code ? some intructions are here: http://doc.sagemath.org/html/en/developer/manual_git.html

About the documentation: you need to indent the examples as follows:

EXAMPLES::

    sage: 1+1 == 2
    True

with 4 spaces.

And also both INPUT: and OUTPUT: must be followed by a blank line.

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

Commit: bab4100

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

Branch: u/TristanVaccon/toy_MatrixF5

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

New commits:

bab4100 Implementation of a toy version of the Matrix F5 algorithm, along with adaptations to stable computations over p-adics and tropical computations.

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

Changed commit from bab4100 to 816f085

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

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

`912aa44`	`Some improvement in spacing examples.`
`816f085`	`Better spacement and indentation.`

fchapoton commented 7 years ago

comment:9

do not use <> but !=
use python3 syntax for print (see https://wiki.sagemath.org/Python3-compatible%20code)
remove commented print lines
There are some tests of if len(something)>0 that could be replaced by if something
missing first line : # -*- coding: utf-8 -*-
The documentation of a function should start by a one-line description, then an empty line, then the rest of the doc.
every function must be doctested, but def sym_pol(n): is not

fchapoton commented 6 years ago

New commits:

`94a3a7d`	`Implementation of a toy version of the Matrix F5 algorithm, along with adaptations to stable computations over p-adics and tropical computations.`
`48a0e4c`	`Some improvement in spacing examples.`
`b5243a2`	`Better spacement and indentation.`
`e9c2544`	`pyflakes and pep8 cleanup`

fchapoton commented 6 years ago

Changed commit from 816f085 to e9c2544

fchapoton commented 6 years ago

Changed branch from u/TristanVaccon/toy_MatrixF5 to public/ticket/20997