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.