F4 algorithm for calculating Groebner bases

[choschech]

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

 

[CoCoA]

I'm afraid I do not know a lot about this algorithm, but I believe that G={f_1,f_2,f_3,f_4} before the second while loop is entered. The first while loop does not stop until F is empty. It is also pretty clear that the labelling of f_1 to f_4 are backwards in the paper on page 14 -- that is, f_4 is in fact a+b+c+d, since the first pair selected with the normal selection strategy will be the pair with head terms ab and a. Howver, given the set T(F_1) in the same paragraph of page 14, only f_4 is needed to reduce the matrix; f_3 can also be used but the reduction it does, of ab, is also done by f_4. The important part is that the other elements of G are not germaine at this point, so perhaps that is why he left them off the dicsussion.

 

[choschech]

Dear CoCoA,

thanks for your answer! I suppose you are right that the first while
loop should be cycled through until F is empty. I rechecked the first part of the
example and came to the same conclusions than you! I am somewhat worried
about the matrix A_1 though (page 14): One column seems to be missing,
the entries for b^2 and d^2 (from bf_4 and df_4) appear to be in the same
column. Do you think there is a mistake in the paper or did I miss something?

I think I should go through the whole example and check whether I am getting a correct solution. I am not sure, however, how to distinguish a correct from a wrong solution. One
problem is that a Groebner basis is not unique so I cannot simply compare my
solution from the F4 algorithm to the solution from a different algorithm. There seems to
be a so-called "reduced" Groebner basis. Do you know whether this is unique?


Best

Luther

 

[CoCoA]

I am frustrated with what I had to do to decipher it. It should have been written more clearly.

One would expect the rows of A to be in the order f_3, bf_4, df_4 sicne that is the order of the set given above the matrix. However, f_3 has two terms each in common with bf_4 and df_4, just as the second has two entries each in common with the first and third rows. Thus the first row is df_4, the second row is f_3, and the third row is bf_4. Then comparing the common terms discloses that the order of the columns is {ab, b^2, bc, ad, bd, cd, d^2, nothing}. Using this order then makes \tilde{A_1} match with f_5, f_6, and f_7.

The most natural way to determine if you got a correct answer, for small examples, is to reduce all the S-polynomials when completed. If they all reduce to zero, then the set is a groebner basis. Or you can feed the set to a computer system with a function like "IsGroebner" to return true if a groebner basis, false otherwise.

 

[choschech]

Thank you once more! I finally get an idea about how to use the F4 algorithm.

Just to make sure I have understood how to check whether a solution really is
a Groebner basis:
Do you mean that I could calculate all possible S-polynomials for the elements
of the solution and that the Normal Forms of these S-polynomials with
respect to this solution would all be zero?


Best

Luther

 

[CoCoA]

Yes, that is a basic characteristic of Groebner bases; you can find in the book by Backer & Weispfenning referred in Faugere's paper or many other introductions to Groebner bases. If you need brushing up, you should look at one of these before getting too deep with a particular algorithm like F4.

 

[choschech]

Thanks CoCoA! You have been great help and I feel confident that I can tackle my problems now!