Content deleted Content added
m moved Faugère F4 algorithm to Faugère's F4 and F5 algorithms: The article concerns two algorithms |
mNo edit summary |
||
Line 7:
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:
<blockquote>
If ''G''<sub>prev</sub> is an already computed Gröbner basis (''f''<sub>2</sub>, …, ''f''<sub>''m''</sub>) and we want to compute a Gröbner basis of (''f''<sub>1</sub>) + ''G''<sub>prev</sub> then we will construct matrices whose rows are ''m''
</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.
| |||