Matrix-F5 algorithms and tropical Gröbner bases computation (Q1635284): Difference between revisions

This paper is a minimal extension of [\textit{T. Vaccon}, in: Proceedings of the 40th international symposium on symbolic and algebraic computation, ISSAC 2015. New York, NY: Association for Computing Machinery (ACM). 355--362 (2015; Zbl 1346.13061)]. The author designs strategies to compute tropical Gröbner bases of homogeneous ideals with respect to a monomial ordering in \(A=K[X_1,\ldots,X_n]\), where \(K\) is a field equipped with a valuation, by adapting the F5 algorithm of Faugère. For example, Algorithm 3.4.1. computes a tropical D-Gröbner basis by tropical row-echelon form computations, but it has already introduced in [loc. cit.] with its complexity. However, as in the classical case, Section 3.7 introduces a new algorithm to compute the reduced tropical Gröbner basis of an homogeneous ideal. Subsection 4.6 analyses the stability of this algorithm over inexact fields with complete, discrete valuations, such as \(Q_p\). This is an important issue because it is known that, in inexact fields, the difficulty lies in certifying when an element is zero or not. Another novelty of the article is Subsection 4.7, which is devoted to the analysis of the loss in precision for the special case \(w = (0,\dots,0)\). Moreover, Section 6 presents more numerical examples than [loc. cit.], showing loss in precision and timings, and an explicit example is provided throughout the article to show how the computations are done, which is always appreciated.