F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases (Q607065)

One of the best algorithm computing Gröbner bases is Faugère's F5 algorithm. This algorithm is incremental, i.e. to compute the Gröbner basis of the ideal generated by the list of polynomials \(F=(F_1,\dots,F_m)\) it computes the Gröbner bases of the ideals \(\langle F_m\rangle\), \(\langle F_{m-1},F_m\rangle\),\dots, \(\langle F_2,\dots,F_m\rangle\). \textit{J.-C. Faugère} [ISSAC 2002. Proceedings of the 2002 international symposium on symbolic and algebraic computation, Lille, France, July 07--10, 2002. New York, NY: ACM Press. 75--83 (2002; Zbl 1072.68664)] proposed to add to each polynomial \(p\) an information, called ``signature'', about how \(p\) is computed from \(F\) and then exploit these informations hereinafter. This strategy turns out to be very efficient, but a analysis of the execution of the algorithm led to think that it could be further improved, because in general F5 reduces also many redundant polynomials useless for the final Gröbner basis. In this paper, the authors present a new strategy, mainly based on the construction of a reduced Gröbner basis instead of a generic one, as for F5. \textit{T. Stegers} [Faugère's F5 Algorithm Revisited (Thesis, Technische Universität Darmstadt, Germany) (2006)] proved that the generic Gröbner basis can not be simply replaced by the reduced basis because such a variant of F5 would be incorrect. The authors consider again reduced bases even ensuring the correctness of the algorithm by updating at each incremental step the signatures, so that this variant returns a reduced Gröbner basis and moreover during the computation it uses only the signatures of the polynomials in such a basis. The computational experiments show that the modified algorithm is a faster and requires less reductions than F5.