Matrix-F5 algorithms and tropical Gröbner bases computation. (November 2018)

• Record Type: Journal Article
• Authors: Vaccon, Tristan
• Is Part Of: Journal of symbolic computation. Volume 89(2018)
• Page Start: 227
• Page End: 254
• Publication Date: 2018-11
• Subjects: Gröbner bases -- Tropical geometry -- F5 algorithm -- p-Adic precision -- p-Adic algorithm; 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.2017.11.014
• 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, this theory is promising for stable computations over polynomial rings over a p -adic field. 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 Q p or F q ( ( t ) ) . 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.