Faugère's F4 and F5 algorithms: Difference between revisions

Revision as of 20:38, 27 June 2010

Revision as of 23:13, 27 April 2011

Line 5:

If ''G''_prev is an already computed Gröbner basis (''f''₂, …, ''f''_''m'') and we want to compute a Gröbner basis of (''f''₁) + ''G''_prev then we will construct matrices whose rows are ''m'' ''f''₁ such that ''m'' is a monomial not divisible by the leading term of an element of ''G''_prev.

</blockquote>

This strategy allows the algorithm to apply two new criteria based on what Faugère calls ''signatures'' of polynomials. Thanks to these criteria, the algorithm can compute Gröbner bases for a large class of interesting polynomial systems, called ''regular sequences'', without ever simplifying a single polynomial to zero--the most time-consuming operation in algorithms that compute Gröbner bases. It is also very effective for a large number of non-regular sequences.

== Implementations ==

Line 12:

* as a [http://www-calfor.lip6.fr/~jcf/Software/FGb package FGb] for the [[Maple computer algebra system]]. This package is included in [[Maple (software)|Maple]] distribution as the option '''method=fgb''' of function '''Groebner[gbasis]'''.

* in the [[Magma computer algebra system]]

* in the [[SINGULAR]] computer algebra system

== Applications ==