The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Math Topics »

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  

Advanced Search

Back to Topic List Back to Topic List  

Posts: 1
From: Germany
Registered: 7/13/09
F4 algorithm for calculating Groebner bases
Posted: Jul 13, 2009 8:51 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply
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?



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.