-- MATH 531 -- Sept 13 -- Home-made Buchberger -- lab2.m2

-- We define three functions, one of which - Buchberger - shall be 
-- used to compute a G.b. for the ideal generated by polynomials F 

-- THE PART THAT SHOULD BE EXECUTED INTERACTIVELY 
-- STARTS AFTER ///

Buchberger = F -> (
     local G,S,i,j,p,f; -- make all the variables used in the routine local 
     -- initialize the current basis
     G = F; 
     -- initialize the queue of s-pairs
     S = {};
     for i from 0 to #G-1 do
     for j from i+1 to #G-1 do
          S = S  | {(G#i,G#j)};
     -- main loop
     while #S>0 do (
	  p = first S; S = drop(S,1); -- pick the first s-pair in S
	  f = reduce(Spoly(p#0,p#1), G);  
	  if f != 0 then (
	       -- "apply" applies a function (second argument)
	       -- to a list (first)
	       S = S | apply(G, g->(g,f));
	       G = G | {f} 
	       )     
	  );
     G
     )

reduce = (f,G) -> (
     while f!=0 and any(G, g->(leadTerm f)%(leadTerm g)==0) do (
	  -- select one element of G s.t. its LT divides the LT(f)
     	  g := select(1, G, g->(leadTerm f)%(leadTerm g)==0);
	  -- the result of the previous operation is a list of one element
	  f = f%(first g);   
	  );
     f
     )

Spoly = (f,g) -> (
     R := ring f;
     -- another way to make a variable local is 
     -- to use ":-" instead of "=" for the first assignment 
     lef := listForm leadMonomial f; 
     leg := listForm leadMonomial g;
     -- "(1)/(2)" here is equivalent to calling apply((1),(2))
     lcm := toList(0..#lef-1) / (i->max(lef#i,leg#i));
     mf := toList(0..#lcm-1) / (i->lcm#i-lef#i);
     mg := toList(0..#lcm-1) / (i->lcm#i-leg#i);
     (1/leadCoefficient f)*R_mf*f - (1/leadCoefficient g)*R_mg*g
     )



-- THIS IS THE END OF BUCHBERGER'S ALGORITHM IMPLEMENTATION
-- BELOW IS AN EXAMPLE THAT USES THE HOME-MADE BUCHBERGER
-- (execute in the interactive mode using F11)

///
-- anything beetween a pair of triple-slashes
-- is treated as one string
-- ( we use this to avoid processing 
--   the lines below when "load" is called )
restart

-- load this file: use the full path to avoid confusion
-- (this will execute the part before ///, thus defining 3 functions)
load "/home/x/leykin/M2/lab2.m2"

R = QQ[x,y];
F = {x^3,x^2*y-y^3};
Buchberger F
gb ideal F -- compare to the built-in command "gb"

-- unassign variables x and y
x = symbol x;
y = symbol y;
-- use a weight order
R = QQ[x,y,Weights=>{1,10}];
F = {x^3,x^2*y-y^3};
Buchberger F
gb ideal F -- compare to the built-in command "gb"

x = symbol x;
y = symbol y;
-- use elimination order w.r.t. x
R = QQ[x,y,MonomialOrder=>Eliminate 1];
F = {x^3,x^2*y-y^3};
Buchberger F
gb ideal F -- compare to the built-in command "gb"
///