Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Luther
Posts:
1
From:
Germany
Registered:
7/13/09


F4 algorithm for calculating Groebner bases
Posted:
Jul 13, 2009 8:51 AM



Dear all,
I have a question concerning Faugere's improved F4 algorithm. You can find it in the attached file faugere_f4.pdf on page 9. In section 2.6 (page 14) an example is given for how the algorithm works.
According to the example the second whileloop in the improved F4 algorithm (page 9) is entered for the first time with the set G={{f_4}}. I do not understand why. Before entering the second whileloop the algorithm runs through the first whileloop for two times calling the Update function each time. I have attached this function in the file update.jpg. As you can see each time the function is called with a particular polynomial h this polynomial will end up in G_new, and thereby in the set G of the F4 algorithm (third to last line in update.jpg). Which polynomial Update is called with depends on the first() function in the F4 algorithm. In my opinion when cycling through the first whileloop first() should return f_4 and then f_3. Thus the set G would have to contain f_3 when the second whileloop is entered. I have specified what I think should be going on in specification.pdf. Could anyone explain to me whether and if so why my reasoning is wrong?
Best
Luther



