MATH 819 course project (10% of grade) Spring 2012.
Demo by Thursday April 12th.  Due Thursday April 19th at 11am.
Late penalty -20% for up to 24 hours late.  Zero after that.

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.

Part 1 (10 marks) Your first task is to implement Buchberger's 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 Buchberger's 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 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;

Part 2 (10 marks) 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 criteria.  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 2 and 3 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:

Part 3 (25 marks) The next problem 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 (5 minutes?) for
  most permutations of {b,p,s,t,w,z}.


  Problem 4 (of Trinks) 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.
  You can use the timelimit command to help you do this.

  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.  Implement the FGLM algorithm.
  Use the 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.  It should be fast.

Part 4 (5 marks) I want you to try a monomial ordering other than lex,
  grlex, and grevlex.  In the implicitization application where 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 on or before April 12th so that I can suggest improvements.
Hand in a Maple a worksheet with your Maple code by April 19th.
You can E-mail me the worksheet to mmonagan@cecm.sfu.ca.
Do not write a report.