MATH 800 course project (10% of grade) Summer 2004. Due Wednesday July 19th. Late penalty -10% for each day late. The goal of this project is to develop a deeper understanding of Buchberger's algorithm and where and how one can improve on it. I expect to have some interaction with you over the course of the project. o Your first task is to implement Buchbergers algorithm and make it output a "reduced" Grobner basis. Check that your implementation is working correctly by comparing it with Maple on some examples. Note that Maple's reduced Grobner basis is normalized differently -- the polynomials in the basis are made primitive over Z rather than monic over Q. Most of the time in Buchbergers algorithm is spent in the division algorithm. To speed it up it will help a lot if you "remember" the leading term of each polynomial so that you don't repeatedly have to compute it in the inner loop of the division algorithm. So store each basis polynomial f in this format: [ LT(f), f ] Also, to avoid a blowup in the rational coefficients make each basis polynomial either monic (i.e. LC(f) = 1) or primitive over Z. To make f primitive over Z in Maple use: f/icontent(f); o Run your implementation on this linear system from section 2.7. You should get the equivalent of the reduced row echelon matrix in (4). Print out the basis after each new polynomial is added to it. Problem 1 in Q[x,y,z,w] f1 := 3*x-6*y-2*z; f2 := 2*x-4*y+4*w; f3 := x-2*y-z-w; o One way to improve the efficiency of Buchberger's algorithm is to identify S-polynomials which will reduce to 0 in advance to eliminate the expensive divisions. Study section 2.9 which details two criteria that can be used to do this. Implement both critera. Count the number of times each criterion is applicable and output this information at the end of the Grobner basis computation, i.e. print the total number of S-polynomials considered and the total number of times each criterion is applicable. Do this for problem 1 and 2 below. o Run your implementation on the following two problems using the lex, grlex and grevlex monomial orderings over some orderings for {x1,x2,x3} and {u0,u1,u2,u3} respectively to check that it is working. Problem 2 in Q[x,y,z] f1 := 4*x^2 + x*y^2 - z + 1/4; f2 := 2*x + y^2*z + 1/2; f3 := x^2*z - 1/2*x - y^2; Problem 3 in Q[u0,u1,u2,u3] f1 := u0^2 - u0 + 2*u1^2 + 2*u2^2 + 2*u3^2: f2 := 2*u0*u1 + 2*u1*u2 + 2*u2*u3 - u1: f3 := 2*u0*u2 + u1^2 + 2*u1*u3 - u2: f4 := u0 + 2*u1 + 2*u2 + 2*u3 - 1: o This third problem of Trinks, in Q[b,s,w,z,t,p]; is hard, even though some of the equations are linear. You should have little difficulty using either grlex or grevlex but you will find that the computation using lex will not terminate in a reasonable time (one hour?) for most permutations of {b,p,s,t,w,z}. Problem 4 in Q[b,s,w,z,t,p] f1 := 45*p + 35*s - 165*b - 36; f2 := 35*p + 40*z + 25*t - 27*s; f3 := 15*w + 25*p*s + 30*z - 18*t - 165*b^2; f4 := -9*w + 15*p*t + 20*z*s; f5 := w*p + 2*z*t - 11*b^3; f6 := 99*w - 11*s*b + 3*b^2; Find some permutations of {b,p,s,t,w,z) which take a long time with lex. I was able to find some which complete in under one minute on a slow computer. You can use the timelimit command to help you do this. o As the Trinks example demonstrates, computing a lex Grobner basis using Buchberger's algorithm is often MUCH harder than computing a grlex or grevlex Grobner basis. Yet the lex ordering is very important because that's what we often want, e.g. for solving a system of polynomial equations and eliminating variables. A different approach to compute a lex Grobner basis is to first compute a grlex or grevlex Grobner basis using Buchberger's algorithm and then to convert this Grobner basis to a Grobner basis with the lex ordering. An algorithm to do this for the finite dimensional case using only linear algebra was discovered by Faugere, Gianni, Lazard, and Mora. It is now called the "FGLM Algorithm" and in general it is much faster than using Buchberger's algorithm directly. Study the supplementary material. Use this algorithm to find a Grobner basis under >lex for one of the orderings your implementation of Buchberger's algorithm for >lex failed to terminate in a reasonable time. o I want you to try a monomial ordering other than lex, grlex, grevlex. In the implicitization application where we we had a polynomial parametrization x1 = f1(t1,...,tm), ..., xn = fn(t1,...,tm), we eliminated t1,...,tm by computing a lex Groebner basis with t1 > ..., tm > x1 > ... > xn. In exercise 5 of 3.1 we see that what we "need" is any monomial ordering of m-elimination type. In exercise 6 of 3.1 it was suggested that we create a product order using grevlex on k[t1,...,tm] and also grevlex on k[x1,...,xn]. It is not hard to see that this idea can be generalized as follows. Suppose we have any monomial ordering >x on k[x1,x2,...,xm] and >y on k[y1,...,yn]. Define x^alpha y^beta >elim x^gamma y^delta <==> x^alpha >x x^gamma or ( x^alpha = x^gamma and y^beta >y y^delta ). This gives us a monomial ordering on k[x1,...,xm,y1,...,yn] of m-elimination type. So in particular, if >x is >lex and >y is >lex then >elim is just >lex with x1 > ... > xm > y1 > ... > yn. Implement the >elim monomial ordering using >grlex and >grlex for >x and >y. Apply it and >lex to the these two problems and others of your choice. Eliminate t,u from { x-t-u, y-t^2-2*t*u, z-t^3-3*t^2*u }. Eliminate t from { t^2+x^2+y^2+z^2, t^2+2*x^2-x*y-z^2, t+y^3-z^2 }. Once you get things working, please give me a demonstration of your work so that I can suggest any improvements. Hand in a Maple worksheet with your Maple code showing the work you have done. You can E-mail me the worksheet to mmonagan@cecm.sfu.ca. Do not write a report.