• This Maple worksheet: examples.mw
• Our slides: grobner_bases.pdf [LaTex source grobner_bases.tex]

>	restart; with(plots): with(LinearAlgebra): with(Groebner);

 

(1)

 

Let's increase the amount of information which Maple displays... 

>	infolevel[GroebnerBasis] := 2:

 

Example: Given a set of polynomials , let's find a reduced Grobner basis relative to several different term orderings. 

>	F := [x^3 - 3*x*y, x^2*y - 2*y^2 + x];

 

(2)

 

>	Basis(F, plex(x,y));  # lexicographic order with x > y

 

 

-> FGb

 

total time:         0.017 sec

 

-> FGLM algorithm total monomials  : 8 total time   (sec) 0.9e-2
	(3)

 

>	Basis(F, tdeg(x,y));

 

 

-> FGb

 

total time:         0.009 sec
	(4)

 

>	Basis(F, grlex(x,y));

 

 

-> F4 algorithm

 

total time:         0.009 sec
	(5)

 

Example: Linear Algebra 

We can solve linear algebra problems with Grobner bases -- in an astoundingly inefficient way! 

>	A := <<1,2,3>|<4,5,6>|<7,8,9>>;

 

(6)

 

Our linear system... 

>	A.<x,y,z> = <18,15,12>;

 

(7)

 

We can make Maple do Gaussian elimination in order to find the solution... 

>	ReducedRowEchelonForm(<A|<18,15,12>>);

 

(8)

 

Now let's solve using a Grobner basis. 

>	Sys := [seq((A.<x,y,z>)[i] - <18,15,12>[i],i=1..3)];

 

(9)

 

>	Basis(Sys,plex(x,y,z));

 

 

-> FGb

 

total time:         0.006 sec -> Groebner Walk

 

total time:         0.003 sec
	(10)

 

So and .  Thus... 

...the same as before. 

What if we reverse the order of the variable (i.e. swap columns in our coefficient matrix)? Say swap and 's positions. 

>	B := <<7,8,9>|<4,5,6>|<1,2,3>>;

 

(11)

 

>	ReducedRowEchelonForm(<B|<18,15,12>>);

 

(12)

 

Now our solution is... 

Our linear polynomials plugged into the basis function are the same... 

>	Sys := [seq((B.<z,y,x>)[i] - <18,15,12>[i],i=1..3)];

 

(13)

 

However, we use a different lexicographic ordering: then then . 

>	Basis(Sys,plex(z,y,x));

 

 

-> Groebner Walk

 

total time:         0.002 sec
	(14)

 

The same as above! 

So the lexicographic ordering effects our answer in the same way as the ordering of our columns in our coefficient matrix does. 

Example: Euclidean Algorithm 

When we compute a reduced Grobner basis for a set of polynomials in 1 variable, we are just finding the greatest common divisor. Buchberger's algorithm in this case is essentially the same as the Euclidean algorithm. 

>	Sys := [(x-5)^2*(x^2+9)^3*x*(x-1),(x-5)*(x^2+9)^2*x*(x+6)^5,x*(x^2+9)];

 

(15)

 

>	Basis(Sys,plex(x));

 

 

-> FGb

 

total time:         0.007 sec
	(16)

 

Example: Points of Intersection 

Let's use a Grobner basis to determine the points of intersection of and . 

>	Sys := [x^2+y^2-25,x*y-1];

 

(17)

 

>	Basis(Sys,plex(x,y));

 

 

-> FGb

 

total time:         0.006 sec -> FGLM algorithm total monomials  : 6 total time   (sec) 0.1e-2
	(18)

 

We get   and . The second equation is quadratic in so it can be solved (by hand)... 

>	ys := [solve(y^4-25*y^2+1=0)];

 

(19)

 

These solutions can then be plugged into to find the -coordinates of the points of intersection. There are 4 such points. 

>	for y in ys do  print('(x,y)' = (simplify(-y^3+25*y),y)); end do;

 

 

 

 

	(20)

 

Decimal approximations of these points... 

>	for y in ys do  print('(x,y)' = (evalf(-y^3+25*y),evalf(y))); end do; y := 'y':

 

 

 

 

	(21)

 

A plot revealing the 4 points... 

>	implicitplot({x^2+y^2=25,x*y=1},x=-5..5,y=-5..5);

 

Example: No Intersection 

The curves , , and have no points in common as we can see in the plot below: 

>	implicitplot({x^2+y^2=25,x*y=1,x^2-y^2=1},x=-5..5,y=-5..5);

 

Let's see if a Grobner basis will reveal this to us... 

>	Sys := [x^2+y^2-25,x*y-1,x^2-y^2-1];

 

(22)

 

>	Basis(Sys,plex(x,y));

 

 

-> FGb

 

total time:         0.007 sec
	(23)

 

We are left with the single element "1" which translates to the equation "1=0". Thus there are no solutions! 

Example: Using Grobner bases to solve integer equations.  

Let's use a Grobner basis to make change (I don't recommend trying to teach this to your average cashier). 

1 penny to a penny (p) 

5 pennies to a nickel (n) 

10 pennies to a dime (d) 

25 pennies to a quarter (q) 

100 pennies to a dollar (b=buck) 

We encode this as... 

and 

>	F := [p^5-n,p^10-d,p^25-q,p^100-b];

 

(24)

 

>	B := Basis(F,grlex(p,n,d,q,b));

 

 

-> F4 algorithm

 

total time:         0.008 sec
	(25)

 

Suppose we have... 

2 dollars, 5 quarters, 2 dimes, 3 nickels, and 8 pennies 

>	Change := b^2*q^5*d^2*n^3*p^8;

 

(26)

 

>	NormalForm(Change, B, grlex(p,n,d,q,b));

 

(27)

 

This is equivalent to... 

3 dollars, 2 quarters, 1 dime, 1 nickel, and 3 pennies. 

(Thinking of the dollar as a coin, we have a total of 3+2+1+1+3=10 coins.) 

What if we use lexicographic ordering instead of degree lex? 

>	F := [p^5-n,p^10-d,p^25-q,p^100-b];

 

(28)

 

>	B := Basis(F,plex(p,n,d,q,b));

 

 

-> Groebner Walk

 

total time:         0.008 sec
	(29)

 

>	Change := b^2*q^5*d^2*n^3*p^8;

 

(30)

 

>	NormalForm(Change, B, plex(p,n,d,q,b));

 

(31)

 

Now our equivalent change is... 

3 dollars, 1 quarter, 4 dimes, 3 pennies, but no nickels. 

This is a total of 3+1+4+3=11 "coins".  

Using the pure lexicographic ordering, the normal form looks for an equivlent (mod our relations) monomial which avoid lower value coins if at all possible. Notice we used 1 more coin, but we avoided having a nickel. We do have some pennies, but this cannot be helped.