On affine tropical F5 algorithms. (January 2021)

• Record Type: Journal Article
• Authors: Vaccon, Tristan; Verron, Thibaut; Yokoyama, Kazuhiro
• Is Part Of: Journal of symbolic computation. Volume 102(2020)
• Page Start: 132
• Page End: 152
• Publication Date: 2021-01
• Subjects: Algorithms -- Tropical geometry -- Gröbner bases -- F5 algorithm -- p-adic precision; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2019.10.012
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p -adic field that are more stable than that of classical Gröbner bases. Beforehand, these strategies were only available for homogeneous polynomials. In this article, we extend the F5 strategy to a new definition of tropical Gröbner bases in an affine setting. We also provide a competitor with an adaptation of the F4 strategy to tropical Gröbner bases computations. We provide numerical examples to illustrate time-complexity and p -adic stability of this tropical F5 algorithm. We also illustrate its merits as a first step before an FGLM algorithm to compute (classical) lex bases over p -adics.