Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Faugère's F4 and F5 algorithms
open-in-new
<p>In <a href="/facts/Computer_algebra/hjun1KAX">computer algebra</a>, the Faugère F4 algorithm, by <a href="/facts/Jean-Charles_Faug%C3%A8re/7C3AuKAS">Jean-Charles Faugère</a>, computes the <a href="/facts/Gr%C3%B6bner_basis/efMrjM7w">Gröbner basis</a> of an <a href="/facts/Ideal_(ring_theory)/vCvytduX">ideal</a> of a multivariate <a href="/facts/Polynomial_ring/ua3vk8Ih">polynomial ring</a>. The algorithm uses the same mathematical principles as the <a href="/facts/Buchberger_algorithm/7z5q4K33">Buchberger algorithm</a>, but computes many normal forms in one go by forming a generally <a href="/facts/Sparse_matrix/FFtN0XjR">sparse matrix</a> and using fast linear algebra to do the reductions in parallel. </p><p>The Faugère F5 algorithm first calculates the Gröbner basis of a pair of generator polynomials of the ideal. Then it uses this basis to reduce the size of the initial matrices of generators for the next larger basis: </p> <p>If <i>G</i>prev is an already computed Gröbner basis (<i>f</i>2, …, <i>f</i><i>m</i>) and we want to compute a Gröbner basis of (<i>f</i>1) + <i>G</i>prev then we will construct matrices whose rows are <i>m</i> <i>f</i>1 such that <i>m</i> is a monomial not divisible by the leading term of an element of <i>G</i>prev. </p> <p>This strategy allows the algorithm to apply two new criteria based on what Faugère calls <i>signatures</i> of polynomials. Thanks to these criteria, the algorithm can compute Gröbner bases for a large class of interesting polynomial systems, called <i><a href="/facts/Regular_sequence/Nxr2uwh7">regular sequences</a></i>, 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. </p>