Extended \(F_5\) criteria
type: Item
instance of: scholarly article
title: Extended \(F_5\) criteria
zbMATH Open document ID: 1218.13014
author: Amir Hashemi
author: Gwénolé Ars
published in: Journal of Symbolic Computation
publication date: 2010-11-19T00:00:00Z
review text: Let \(R = K[x_1,\dots,x_n]\) be a polynomial ring with coefficients in a computable field \(K\) and let \(I\) be the ideal generated by the polynomials \(f_1,\dots,f_k\). \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)] gave an optimal criterion to compute the Gröbner basis of \(I\) with respect to a term ordering \(<\) and projected a very efficient algorithm called \(F_5\). \(F_5\) is incremental, that is to compute the Gröbner basis of \(I = \langle f_1,\dots,f_k\rangle\), \(F_5\) computes successively the Gröbner basis of the ideals \(\langle f_k\rangle\), \(\langle f_{k-1},f_k\rangle\), \dots, \(\langle f_1,\dots,f_k\rangle\), and its efficiency is due to \(F_5\) criteria, for which the algorithm assigns to any polynomial of \(R\) a signature, that is an element of the module \(R^k\), and that explain how to take advantage of this additionally structure. Hence the quickness of the computation can be affected by the order of the generators and by the module ordering defined on \(R^k\). In this paper the authors modify \(F_5\) criteria considering module orderings coinciding with the term ordering \(<\) of \(R\) on any restriction to a summand of the module \(R^k\). These new criteria lead to an algorithm no more incremental and so not depending on the order of the generators of the ideal. The authors conduct tests on some challenging examples to compare their new proposal with \(F_5\). From this experimental comparison, the new algorithm turns out to be more stable and a little faster than \(F_5\).
reviewed by: Paolo Lella
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 5817626
zbMATH Keywords: Gröbner bases
zbMATH Keywords: \(F_5\) algorithm
zbMATH Keywords: \(F_5\) criteria
describes a project that uses: Magma
MaRDI profile type: Publication
full work available at URL: j.jsc.2010.06.013
OpenAlex ID: W1576188537
cites work: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
cites work: Q3208084
cites work: Q3714165
cites work: Q4693774
cites work: Q4247789
cites work: A new efficient algorithm for computing Gröbner bases \((F_4)\)
cites work: Q4660688
cites work: Q3325833
cites work: The complexity of the word problems for commutative semigroups and polynomial ideals
cites work: Q4234258
DOI: 10.1016/J.JSC.2010.06.013
description: scientific article; zbMATH DE number 5817626