Back to Search Start Over

Matrix-F5 algorithms and tropical Gröbner bases computation

Authors :
Tristan Vaccon
Institut de Recherche Mathématique de Rennes ( IRMAR )
Université de Rennes 1 ( UR1 )
Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 )
Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS )
Institut de Recherche Mathématique de Rennes (IRMAR)
Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes)
Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest
Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)
AGROCAMPUS OUEST
Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1)
Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2)
Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes)
Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)
Source :
International Symposium on Symbolic and Algebraic Computation, ISSAC 2015, International Symposium on Symbolic and Algebraic Computation, ISSAC 2015, Jul 2015, Bath, United Kingdom. 〈10.1145/2755996.2756665〉, International Symposium on Symbolic and Algebraic Computation, ISSAC 2015, Jul 2015, Bath, United Kingdom. ⟨10.1145/2755996.2756665⟩
Publication Year :
2018
Publisher :
Elsevier BV, 2018.

Abstract

International audience; Let $K$ be a field equipped with a valuation. Tropical varieties over $K$ can be defined with a theory of Gröbner bases taking into account the valuation of $K$. Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a $p$-adic fields.We design a strategy to compute such tropical Gröbner bases by adapting the Matrix-F5 algorithm. Two variants of the Matrix-F5 algorithm, depending on how the Macaulay matrices are built, are available to tropical computation with respective modifications. The former is more numerically stable while the latter is faster.Our study is performed both over any exact field with valuation and some inexact fields like $\mathbb{Q}_p$ or $\mathbb{F}_q \llbracket t \rrbracket.$ In the latter case, we track the loss in precision, and show that the numerical stability can compare very favorably to the case of classical Gröbner bases when the valuation is non-trivial. Numerical examples are provided.

Details

ISSN :
07477171
Volume :
89
Database :
OpenAIRE
Journal :
Journal of Symbolic Computation
Accession number :
edsair.doi.dedup.....4d856b759281da007f69544e2b5d0da0
Full Text :
https://doi.org/10.1016/j.jsc.2017.11.014