On Affine Tropical F5 Algorithms

DOI10.1145/3208976.3209012MaRDI QIDQ5120220zbMATH OpenOpenAlexWikidataFDO

Authors Tristan Vaccon, Thibaut Verron, Kazuhiro Yokoyama

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.06183

zbMATH Keywords

\(p\)-adic precisionalgorithmsF5 algorithmGröbner basestropical geometry

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Foundations of tropical geometry and relations with algebra (14T10) Symbolic computation and algebraic computation (68W30)

Abstract: Let $K$ be a field equipped with a valuation. Tropical varieties over $K$ can be defined with a theory of Gr{"o}bner bases taking into account the valuation of $K$.Because of the use of the valuation, the theory of tropical Gr{"o}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{"o}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{"o}bner bases in an affine setting.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.

Recommendations

• On affine tropical F5 algorithms
• A tropical F5 algorithm
• On FGLM algorithms with tropical Gröbner bases
• Tropicalizing the simplex algorithm
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Computer algebra methods in tropical geometry
• New algorithms for solving tropical linear systems
• Tropical Convex Hull Computations

Cited in

(6)

• Complexity bounds on Semaev's naive index calculus method for ECDLP
• Computing tropical varieties over fields with valuation
• On affine tropical F5 algorithms
• Solving \(p\)-adic polynomial systems via iterative eigenvector algorithms
• A tropical F5 algorithm
• Axioms for a theory of signature bases

This page was built for publication: On Affine Tropical F5 Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120220)