The F5 criterion revised

DOI10.1016/J.JSC.2011.05.004MaRDI QIDQ2275900zbMATH OpenOpenAlexFDO

Authors Alberto Arri, John Perry

Publication date 10 August 2011

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

\texttt{Sage}F5 Gröbner bases syzygies

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Abstract: The purpose of this work is to generalize part of the theory behind Faugere's "F5" algorithm. This is one of the fastest known algorithms to compute a Groebner basis of a polynomial ideal I generated by polynomials f_{1},...,f_{m}. A major reason for this is what Faugere called the algorithm's "new" criterion, and we call "the F5 criterion"; it provides a sufficient condition for a set of polynomials G to be a Groebner basis. However, the F5 algorithm is difficult to grasp, and there are unresolved questions regarding its termination. This paper introduces some new concepts that place the criterion in a more general setting: S-Groebner bases and primitive S-irreducible polynomials. We use these to propose a new, simple algorithm based on a revised F5 criterion. The new concepts also enable us to remove various restrictions, such as proving termination without the requirement that f_{1},...,f_{m} be a regular sequence.

Review text

Gröbner bases have played a crucial role in commutative algebra and many scientists had tried to improve the original Buchberger's algorithm and to detect useless computations [\textit{B. Buchberger}, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideals. Ph.D. Thesis, University of Innsbruck. (1965); Lect. Notes Comput. Sci. 72, 3--21 (1979; Zbl 0417.68029); \textit{R. Gebauer} and \textit{M. Möller}, J. Symb. Comput. 6, No. 2/3, 275-286 (1988; Zbl 0675.13013); \textit{D. Lazard}, Lect. Notes Comput. Sci. 162, 146--156 (1983; Zbl 0539.13002)]. The authors present a simpler algorithm that illustrates the principle of the Faugère's ``F5 algorithm and enables to remove various restrictions. By considering a function \(s\), the authors define new concepts such as primitive \(s\)-irreducible polynomials and \(s\)-Gröbner bases. From this new theory, it is developed a simpler algorithm which computes a \(s\)-Gröbner basis of an ideal. This new algorithm is different from the Faugère's algorithm and does not involve reductions that yield more than one result. In the end of the paper, the authors compare this algorithm with the Staggered Linear Basis algorithm of \textit{R. Gebauer} and \textit{M. Möller} [Buchberger's algorithm and staggered linear bases. in: Proceedings of SYMSAC 1986, Waterloo/Ontario, ACM Press. 218--221 (1986)] and with the \textit{J.-C. Faugère}'s ``F5 criterion [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)].

Recommendations

Cites work

Cited in

(33)

Describes a project that uses

Uses Software

SageMath

This page was built for publication: The F5 criterion revised

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