Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: F4 algorithm for calculating Groebner bases
Replies: 0

 Luther Posts: 1 From: Germany Registered: 7/13/09
F4 algorithm for calculating Groebner bases
Posted: Jul 13, 2009 8:51 AM
 update.jpg (672.0 K) faugere_f4.pdf (316.4 K) specification.pdf (24.4 K)

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 while-loop 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 while-loop the algorithm runs through the first while-loop 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 while-loop first() should return f_4 and then f_3. Thus the set G would have to contain f_3 when the second while-loop 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