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

Revision as of 13:39, 5 February 2013

Revision as of 17:06, 29 March 2013

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 sequence]]s'', without ever simplifying a single polynomial to zero--thezero—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 57:

* [http://www.broune.com/papers/f4.pdf An introduction to the F4 algorithm.]

{{DEFAULTSORT:Faugere's F4 and F5 algorithms}}

{{algorithm-stub}}

[[Category:Computer algebra]]

{{algorithm-stub}}