{VERSION 3 0 "SUN SPARC SOLARIS" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 256 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE " " -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 306 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 307 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{PSTYLE "Norm al" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "M aple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 256 0 "" }{TEXT 257 29 "Tutorial for the gbr5 package" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "By William Gryc, Amherst College" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 843 " Well, you finally di d it. After hours of deliberation and procrastination, you have final ly downloaded and saved the gbr5 files on your computer, just like you r professor asked you to. Now you are expecting a long-winded and com plex tutorial. Well, you aren't getting it here! This tutorial is de signed to be clear and quick, so you can start working as soon as poss ible. If you want longer explanations, try looking at the help access ed by opening the worksheet \"gbr5hlp.mws\" which, hopefully, you also downloaded. You'll be sure to find whatever you want to know there. \+ Also, please be advised that some of the commands in the package are \+ slow compared to regular Maple commands, but they should be adequate i n computing the simpler examples in \"Ideals, Varieties, and Algorithm s.\" But, now in the spirit of being quick, onto...." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 26 "The Basics: Loading `gbr5'" }}{PARA 0 "" 0 "" {TEXT -1 344 "Even though you managed to get this tutorial to run ning, that's not all there is to it. There's still the issue of loadi ng the package. This is not too terribly difficult, however. Be sure you've also downloaded \"gbr5.mpl\", \"gbr5hlp.mws\". Then, assuming that you started Maple from the directory containing these files, the n all you type is" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "read(`gbr5.mpl`):" }}{PARA 7 "" 1 "" {TEXT -1 32 "Warning, new definition for norm" }}{PARA 7 "" 1 "" {TEXT -1 33 "Warning, new definition for trace" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 247 "Please note that to use the interactive tutorial, you ju st have to press Enter (or Return, depending on your keyboard) on each Maple input line. After hitting Enter on the previous Maple input li ne, the package is loaded and we are ready to work." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 124 "Also note that reading in \"gbr5.mpl\" generat es two warning messages concerning norm and trace. These can be safel y ignored." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 27 "ring() and Relate d Commands" }}{PARA 0 "" 0 "" {TEXT -1 567 "The most basic command in \+ the package is ring(). This command sets the ring and the monomial or der (see Chapter 2, Section 2 of the text) which most other commands i n the will use. In fact, if you try to use any commands without first setting ring(), you'll get a nasty error message saying that you must set ring() first. The arguments for ring() are a monomial order and \+ a variable list. The valid monomial orders are lex, grlex, grevlex (s ee Chapter 2 Section 2), [k,n] (the kth elimination order on n variabl es; see Exercise 12d in Chapter 2 Section 2), and [" }{TEXT 268 2 "v1 " }{TEXT -1 5 ",...," }{TEXT 269 2 "vn" }{TEXT -1 168 "]. The last or der is a matrix order and is not discussed in the text explicitly. Sa y you were working in the ring k[x1,...,xn]. Then a matrix order woul d consist of " }{TEXT 260 1 "n" }{TEXT -1 31 " linearly independent ve ctors \{" }{TEXT 258 2 "v1" }{TEXT -1 5 ",...," }{TEXT 259 2 "vn" } {TEXT -1 17 "\} each of length " }{TEXT 261 2 "n," }{TEXT -1 13 " such that x^" }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 5 " > x^" } {XPPEDIT 18 0 "beta;" "6#%%betaG" }{TEXT -1 5 " iff " }{TEXT 262 2 "v1 " }{TEXT -1 1 "*" }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 3 " > " }{TEXT 263 3 "v1*" }{XPPEDIT 18 0 "beta;" "6#%%betaG" }{TEXT -1 4 " or " }{TEXT 264 2 "v1" }{TEXT -1 1 "*" }{XPPEDIT 18 0 "alpha;" "6#%&a lphaG" }{TEXT -1 3 " = " }{TEXT 265 3 "v1*" }{XPPEDIT 18 0 "beta;" "6# %%betaG" }{TEXT -1 5 " and " }{TEXT 266 2 "v2" }{TEXT -1 1 "*" } {XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 3 " > " }{TEXT 267 2 "v2 " }{TEXT -1 1 "*" }{XPPEDIT 18 0 "beta;" "6#%%betaG" }{TEXT -1 351 " , etc. All monomials orders the package deals with can be written as m atrix orders. As you will see in a moment, this is how the package se ts monomial orders (except for lex and grevlex, which use the built in Maple orders plex and tdeg, respectively). So, say you wanted to set the ring k[x,y,z] and use the monomial order grevlex. So, you type \+ " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "ring(grevlex, [x,y,z]); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 119 "Then you change your mind and decide on a matrix \+ order with the simplest linearly independant vectors you can think of. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "ring([[1,0,0],[0,1,0],[ 0,0,1]], [x,y,z]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 183 "Notice that grevlex was not cap italized. This is important, as lex, grlex, and grevlex must be enter ed exactly as shown here, in all lower case letters, for ring() to wor k correctly." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 531 "The ring() commands creates term orders in two ways. For lex \+ and grevlex, it uses the terms orders plex and tdeg from the Groebner \+ package. However, for grlex and elimination orders, ring() uses matri ces created by the grlex() and elimination() commands. These are the \+ \"related commands\" that the section title refers to. The lone argum ent for grlex() is the integer that is the number of variables in the \+ ring. So, if we were working in k[x1,x2,x3,x4] and wanted the matrix \+ that yields grevlex order over this ring, we'd type" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "grlex(4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7&7&\"\"\"F%F%F%7&F%\"\"!F'F'7&F'F%F'F'7&F'F'F%F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 206 "Notice that grlex(), as well as elimination(), does not depend on the current ring and monomial order set by ring(). elimination() works differently; it needs one extra argument. The \+ form is elimination(" }{TEXT 270 3 "k,n" }{TEXT -1 9 "), where " } {TEXT 271 1 "n" }{TEXT -1 44 " is the number of variables in the ring \+ and " }{TEXT 272 1 "k" }{TEXT -1 175 " is the number of variables to e liminate. So, to get the matrix that gives a monomial order that elim inates the first three variables of a ring with five variables, you en ter" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "elimination(3,5);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#7'7'\"\"\"F%F%\"\"!F&7'F&F&F&F%F%7'F& F&F&F&!\"\"7'F&F&F)F&F&7'F&F)F&F&F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "And you have your matrix." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 22 "The Division Algorithm" }}{PARA 0 "" 0 "" {TEXT -1 482 "One of \+ the major steps in computing Groebner bases is computing remainders vi a the Division algorithm. The command div_alg() implements this algor ithm. The two arguments of div_alg are a polynomial and a set of poly nomials. div_alg returns a list with two elements: the first element is the remainder, and the second is a list of quotients, ordered in c orrespondence with the ordering of the given set of polynomials. Let' s use Problem 1a in Chapter 2 Section 3 for an example." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "ring(grlex, [x,y]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "div_alg(x^7*y^2 + x^3*y^2 - y + 1, [x*y^2 - x, x - y^ 3]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,**$)%\"xG\"\"(\"\"\"\"\"\"* $)F'\"\"$F)F*%\"yG!\"\"F*F*7$,&*$)F'\"\"'F)F**$)F'\"\"#F)F*\"\"!" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Notice div_alg() divides with resp ect to the term order set by ring()." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 41 "Computing Groebner Bases without Matrices" }}{PARA 0 "" 0 "" {TEXT -1 465 "This package provides four different ways to comput e Groebner bases. The first, slowbasis_gb implements a naive version \+ of Buchberger's algorithm (see Chapter 2 Section 2). The parameter of this command is a list of polynomials [f1,...,fs] slowbasis_gb then \+ returns a list of polynomials that form a Groebner basis for with respect to the termorder set by ring. For an example, we'll u se Exercise 2b from Chapter 2 Section 7. First we set the ring." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "ring(lex, [x,y]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "Then we find the Groebner basis." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "slowbasis_gb([x^2 + y, x^4 + 2*x^2*y + y^2 + 3]) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%0Current~basis:~G7$,&*$)%\"xG\" \"#\"\"\"\"\"\"%\"yGF,,**$)F)\"\"%F+F,*&F(F+F-F,F**$)F-F*F+F,\"\"$F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7#!\"$" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%3Local~divisions:~1G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%3Local~divisi ons:~2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%=Total~divisions~performed :~3G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,&*$)%\"xG\"\"#\"\"\"\"\"\"% \"yGF*,**$)F'\"\"%F)F**&F&F)F+F*F(*$)F+F(F)F*\"\"$F*!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 165 "Notice that the steps of calculation wer e also printed out, as well as how many divisions were performed. To \+ prevent this, just type \"nosteps\" as a second argument." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "slowbasis_gb([x^2 + y, x^4 + 2*x^2* y + y^2 + 3], nosteps);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,&*$)%\"x G\"\"#\"\"\"\"\"\"%\"yGF*,**$)F'\"\"%F)F**&F&F)F+F*F(*$)F+F(F)F*\"\"$F *!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "Sometimes slowbasis_gb g ets out of hand. Consider this example:. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "ring(grevlex, [x,y,z]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "basisprime := [x^3 - z^2, y^3 + z, x^2*y + x*y^2];" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%+basisprimeG7%,&*$)%\"xG\"\"$\"\"\"\"\"\"*$)% \"zG\"\"#F+!\"\",&*$)%\"yGF*F+F,F/F,,&*&)F)F0F+F5F,F,*&F)F,)F5F0F+F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "slowbasis_gb(basisprime); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%0Current~basis:~G7%,&*$)%\"xG\" \"$\"\"\"\"\"\"*$)%\"zG\"\"#F+!\"\",&*$)%\"yGF*F+F,F/F,,&*&)F)F0F+F5F, F,*&F)F,)F5F0F+F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7$,&*& %\"yG\"\"\")%\"zG\"\"#\"\"\"!\"\"*&%\"xGF)F+F)F.,&*&)F0F,F-F+F-F)*(F(F -F0F-F+F-F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%3Local~divisions:~3G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7&,&*$)%\"zG\"\"$\"\"\"! \"\"*(F)\"\"\"%\"xGF.)%\"yG\"\"#F+F.F&,&F'F.F-F,F&" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%3Local~divisions:~7G" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7.,&*&%\"xG\"\"\")%\"zG\"\"$\"\"\"F)*&F(F-)F+\"\"#F-! \"\"F&,&F'F1F.F)F&,&*$)F+\"\"%F-F1*$F*F-F)F3,&F4F)F7F1F3F&F&F2F&" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%4Local~divisions:~26G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# %5Local~divisions:~174G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%?Total~div isions~performed:~210G" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#77,&*$)%\"xG \"\"$\"\"\"\"\"\"*$)%\"zG\"\"#F)!\"\",&*$)%\"yGF(F)F*F-F*,&*&)F'F.F)F3 F*F**&F'F*)F3F.F)F*,&*&F3F)F,F)F/*&F'F)F-F*F/,&*&F6F)F-F)F**(F3F)F'F)F -F)F*,&*$)F-F(F)F/*(F-F)F'F)F8F)F*F?,&F@F*FBF/F?,&*&F'F)FAF)F**&F'F)F, F)F/FD,&FEF/FFF*FD,&*$)F-\"\"%F)F/F@F*FH,&FIF*F@F/FHFDFDFGFD" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 338 "The returned basis is quite unnec essarily repetitive. The reason for this repetition is that the algor ithm is using G' as opposed to G is division (see Buchberger's algorit hm in Chapter 2 Section 7). A second command, altbasis_gb uses G inst ead. Notice that the repetion is now gone, and the number of division s decreases dramatically." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "altbasis_gb(basisprime);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%0Cur rent~basis:~G7%,&*$)%\"xG\"\"$\"\"\"\"\"\"*$)%\"zG\"\"#F+!\"\",&*$)%\" yGF*F+F,F/F,,&*&)F)F0F+F5F,F,*&F)F,)F5F0F+F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7$,&*&%\"yG\"\"\")%\"zG\"\"#\"\"\"!\"\"*&%\" xGF)F+F)F.,&*&)F0F,F-F+F-F)*(F(F-F0F-F+F-F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%3Local~divisions:~3G" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#(%(Added:~G7#,&*$)%\"zG\"\"$\"\"\"!\"\"*(F)\"\"\"%\"xGF.)%\"yG\"\"#F +F." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%3Local~divisions:~7G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7$,&*&%\"xG\"\"\")%\"zG\"\"$\"\" \"F)*&F(F-)F+\"\"#F-!\"\",&*$)F+\"\"%F-F1*$F*F-F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%3Local~divisions:~5G" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#(%(Added:~G7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%4Local~divisions: ~13G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%>Total~divisions~performed:~2 8G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7*,&*$)%\"xG\"\"$\"\"\"\"\"\"*$) %\"zG\"\"#F)!\"\",&*$)%\"yGF(F)F*F-F*,&*&)F'F.F)F3F*F**&F'F*)F3F.F)F*, &*&F3F)F,F)F/*&F'F)F-F*F/,&*&F6F)F-F)F**(F3F)F'F)F-F)F*,&*$)F-F(F)F/*( F-F)F'F)F8F)F*,&*&F'F)FAF)F**&F'F)F,F)F/,&*$)F-\"\"%F)F/F@F*" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 279 "While altbasis_gb() can dramatica lly improve performance, we can still do better. The quickbasis_gb() \+ command implements the improvements to Buchberger's algorithm as detai led in Chaptert 2 Section 9. Let's use two examples to show how quick basis_gb can outperform altbasis_gb:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "basis1 := [x^2, y^4];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'basis1G7$*$)%\"xG\"\"#\"\"\"*$)%\"yG\"\"%F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "altbasis_gb(basis1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%0Current~basis:~G7$*$)%\"xG\"\"#\"\"\"*$)%\"yG\"\"%F* " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%3Local~divisions:~1G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%=Total~divisions~performed:~1G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$*$)%\"xG\"\"#\"\"\"*$)%\"yG\"\"%F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "quickbasis_gb(basis1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%0Current~Basis:~G7$*$)%\"xG\"\"#\"\"\"*$)%\"yG\"\"%F*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%=Total~divisions~performed:~0G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7$*$)%\"xG\"\"#\"\"\"*$)%\"yG\"\"%F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 283 "Clearly, basis1 is already a G roebner basis by definition, and yet altbasis_gb() still performs a di vision. quickbasis_gb() cuts out this division by noticing that x^2 a nd y^4 are relatively prime, and thus no divisons need to be performed (see Propostion 4 of Chapter 2 Section 9)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "basis2 := [x^2, x*y^3, x^2*y^3];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'basis2G7%*$)%\"xG\"\"#\"\"\"*&F(\"\"\")%\"yG\"\"$ F**&F'F*F-F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "altbasis_gb (basis2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%0Current~basis:~G7%*$)% \"xG\"\"#\"\"\"*&F(\"\"\")%\"yG\"\"$F**&F'F*F-F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%(Added:~G7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%3Loc al~divisions:~3G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%=Total~divisions~ performed:~3G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%*$)%\"xG\"\"#\"\"\" *&F&\"\"\")%\"yG\"\"$F(*&F%F(F+F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "quickbasis_gb(basis2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#(%0Current~Basis:~G7%*$)%\"xG\"\"#\"\"\"*&F(\"\"\")%\"yG\"\"$F** &F'F*F-F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%=Total~divisions~perform ed:~2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%*$)%\"xG\"\"#\"\"\"*&F&\" \"\")%\"yG\"\"$F(*&F%F(F+F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 319 "A gain, quickbasis_gb() is able to cut out a division, even though none \+ of the leading terms of basis2 are relatively prime. However, notice \+ that the third leading term, x^2y^3, divides the LCM of x^2 and xy^3 ( in fact, x^2y^3 is the LCM of x^2 and xy^3). By Propostion 10 of Chap ter 2 Section 9, if the remainders of " }{TEXT 273 1 "S" }{TEXT -1 16 "(x^2, xy^3) and " }{TEXT 274 1 "S" }{TEXT -1 52 "(x^2, x^2y^3) are bo th calculated, the remainder of " }{TEXT 275 1 "S" }{TEXT -1 100 "(xy^ 3, x^2y^3) need not be calculated. Thus, quickbasis_gb is implementin g this second improvement." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 198 "It should be noted, however, that Maple's built- in gbasis() command is faster than quickbasis_gb(). However, quickbas is_gb() should be fast enough for most of the examples and problems in the text." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 38 "Minimizing and Red ucing Groebner bases" }}{PARA 0 "" 0 "" {TEXT -1 160 "For added conven ience, there are also commands to minimize and reduce your computed Gr oebner bases. For an example, let's use Problem 9 of Chapter 2 Sectio n 7." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "ring(lex, [x,y,z,w]) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "basis := [3*x - 6*y - 2*z, 2*x - 4*y + 4*w, x - 2*y - z - w];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&basisG7%,(%\" xG\"\"$%\"yG!\"'%\"zG!\"#,(F'\"\"#F)!\"%%\"wG\"\"%,*F'\"\"\"F)F,F+!\" \"F0F4" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "basisprime := qui ckbasis_gb(basis, nosteps);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+basi sprimeG7&,(%\"xG\"\"$%\"yG!\"'%\"zG!\"#,(F'\"\"#F)!\"%%\"wG\"\"%,*F'\" \"\"F)F,F+!\"\"F0F4,&F+F/F0!#7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 208 "To get a minimal Groebner basis from this, we can use the min_gb( ) command. min_gb() takes a list of polynomials that form a Groebner \+ basis under ring() as its lone argument. So, to make basisprime minim al," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "basisprime :=min_gb( basisprime);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+basisprimeG7$,*%\"x G\"\"\"%\"yG!\"#%\"zG!\"\"%\"wGF,,&F+!\"%F-!#7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 336 "Getting a reduced Groebner basis from this new basi sprime, we use the red_gb command. red_gb() takes a list of polynomia ls that for a MINIMAL Groebner basis under ring() as its argument. If the basis isn't a minimal Groebner basis, red_gb() will protest and w ill refuse to do its job. So, to make basisprime a reduced Groebner b asis," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "red_gb(basisprime) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,(%\"xG\"\"\"%\"yG!\"#%\"wG\"\" #,&%\"zGF&F)\"\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "And the Groe bner basis is reduced." }}}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 38 "Comp uting Groebner Bases with Matrices" }}{PARA 0 "" 0 "" {TEXT -1 60 "Con sider the following type of problem: You have an ideal <" }{TEXT 284 9 "f1,...,fs" }{TEXT -1 40 "> and compute a Groebner basis for it, \{ " }{TEXT 285 9 "g1,...,gt" }{TEXT -1 12 "\}. Since <" }{TEXT 286 9 " f1,...,fs" }{TEXT -1 5 "> = <" }{TEXT 287 9 "g1,...,gt" }{TEXT -1 12 " >, for each " }{TEXT 288 2 "fi" }{TEXT -1 15 ", there exists " }{TEXT 289 9 "a1,...,at" }{TEXT -1 11 " such that " }{TEXT 290 2 "fi" }{TEXT -1 3 " = " }{TEXT 291 4 "a1g1" }{TEXT -1 3 " + " }{TEXT 292 4 "a2g2" } {TEXT -1 9 " + ... + " }{TEXT 293 4 "atgt" }{TEXT -1 65 ", and vice ve rsa. For the first problem, it is easy to find the " }{TEXT 294 9 "a1 ,...,at" }{TEXT -1 8 " since \{" }{TEXT 296 8 "g1,..,gt" }{TEXT -1 55 "\} is a Groebner basis the division algorithm gives the " }{TEXT 295 2 "ai" }{TEXT -1 301 ". There is a function in the package, quot_mx() , that does exactly this. quot_mx() takes two arguments. The first i s a list of polynomials that generate an ideal, the second is a Groebn er basis under the termorder set in ring() that generates the same ide al. The output is a matrix Q where Q is a " }{TEXT 303 1 "s" }{TEXT -1 3 " x " }{TEXT 304 1 "t" }{TEXT -1 12 " matrix and " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 1 "[" }{TEXT 297 2 "f1" }{TEXT -1 15 "] [" }{TEXT 300 2 "g1" }{TEXT -1 1 "]" }} {PARA 0 "" 0 "" {TEXT -1 1 "[" }{TEXT 298 2 "f2" }{TEXT -1 15 "] \+ [" }{TEXT 301 2 "g2" }{TEXT -1 1 "]" }}{PARA 0 "" 0 "" {TEXT -1 20 "[...] = Q * [...]" }}{PARA 0 "" 0 "" {TEXT -1 24 "[...] \+ [...]" }}{PARA 0 "" 0 "" {TEXT -1 1 "[" }{TEXT 299 2 "fs" } {TEXT -1 16 "] [" }{TEXT 302 2 "gt" }{TEXT -1 1 "]" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "Consider \+ the following example:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "ri ng(grevlex, [x,y,z]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "gbase := quickbasis_gb( [x - z^4, y - z^5], nosteps);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&gb aseG7(,&%\"xG\"\"\"*$)%\"zG\"\"%\"\"\"!\"\",&%\"yGF(*$)F+\"\"&F-F.,&*& F+F(F'F(F.F0F(,&*$)F'\"\"#F-F.*&)F+\"\"$F-F0F(F(,&*&)F+F9F-)F0F9F-F(*$ )F'F " 0 "" {MPLTEXT 1 0 40 "Q := quot_mx([x - z^4, y - z^5], gbase);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG-%'matrixG6#7$7(\"\"\"\"\"!F+F+F+F+7(%\"z GF+F*F+F+F+" }}}{PARA 0 "" 0 "" {TEXT -1 133 "Notice that Q is not uni que, as the most obvious choice for Q is not the matrix given. Let's \+ verify that Q has the desired property." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "base := matrix(6,1,gbase);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%baseG-%'matrixG6#7(7#,&%\"xG\"\"\"*$)%\"zG\"\"%\"\" \"!\"\"7#,&%\"yGF,*$)F/\"\"&F1F27#,&*&F/F,F+F,F2F5F,7#,&*$)F+\"\"#F1F2 *&)F/\"\"$F1F5F,F,7#,&*&)F/F@F1)F5F@F1F,*$)F+FCF1F27#,&*&)F5FCF1F/F1F, *$)F+F0F1F2" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "simplify(multiply(Q,base));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7$7#,&%\"xG\"\"\"*$)%\"zG\"\"%\"\"\"!\"\"7# ,&%\"yGF**$)F-\"\"&F/F0" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 43 "The opposite question of how to represent \{" } {TEXT 305 9 "g1,...,gt" }{TEXT -1 6 "\} in <" }{TEXT 306 9 "f1,...,fs " }{TEXT -1 133 "> is trickier, since the division algorithm can't do \+ the job in this case. However, you can compute the matrix while compu ting the \{" }{TEXT 307 8 "g1,..,gt" }{TEXT -1 321 "\}. Computing Groe bner bases with matrices isn't a whole lot different than computing th em without matrices (that is, from the user's standpoint). You still \+ use the ring() command to set the term-ordering. However, you just us e one command, mxgb(), to compute a reduced Groebner basis and its mat rix M. The matrix M an " }{TEXT 277 1 "t" }{TEXT -1 3 " x " }{TEXT 276 1 "s" }{TEXT -1 17 " matix such that:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 1 "[" }{TEXT 278 2 "g1" }{TEXT -1 15 " ] [" }{TEXT 281 2 "f1" }{TEXT -1 1 "]" }}{PARA 0 "" 0 "" {TEXT -1 1 "[" }{TEXT 279 2 "g2" }{TEXT -1 15 "] [" } {TEXT 282 2 "f2" }{TEXT -1 1 "]" }}{PARA 0 "" 0 "" {TEXT -1 20 "[...] \+ = M * [...]" }}{PARA 0 "" 0 "" {TEXT -1 24 "[...] [... ]" }}{PARA 0 "" 0 "" {TEXT -1 1 "[" }{TEXT 280 2 "gt" }{TEXT -1 16 "] \+ [" }{TEXT 283 2 "fs" }{TEXT -1 1 "]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 278 "mxgb() takes a list of p olynomials as its argument. If you do not desire to see the basis and matrix at each \"step\" (at the unminimized step, and the unreduced s teps), a second argument of \"nosteps\" should be added. Let's use Pr oblem 2c of Chapter 2 Section 7 as an example. " }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 25 "ring(grevlex, [x, y, z]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%+term_orderG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "mxbase := mxgb([x - z^4, y - z^5]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%4Unminimized~basis:~G7(,&%\"xG\"\"\"*$)%\"zG\"\"%\"\" \"!\"\",&%\"yGF'*$)F*\"\"&F,F-,&*&F*F'F&F'F-F/F',&*$)F&\"\"#F,F-*&)F* \"\"$F,F/F'F',&*&)F*F8F,)F/F8F,F'*$)F&F;F,F-,&*&)F/F;F,F*F,F'*$)F&F+F, F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%5Unminimized~matrix:~G-%'matrix G6#7(7$\"\"\"\"\"!7$F*F)7$,$%\"zG!\"\"F)7$,&%\"xGF/*$)F.\"\"%\"\"\"F/* $)F.\"\"$F67$,(*&F8F6%\"yGF)F/*$)F2\"\"#F6F/*&F4F6F2F)F/,&*&)F.F@F6F=F 6F)*&F2F6F8F6F)7$,**&FDF6)F=F@F6F/*(F2F6F8F6F=F6F/*$)F2F9F6F/*&F4F6F?F 6F/,(*&FIF6F.F)F)*(F2F6FDF6F=F6F)*&F?F6F8F6F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%2Minimized~basis:~G7',&%\"xG\"\"\"*$)%\"zG\"\"%\"\"\"! \"\",&*&F*F'F&F'F-%\"yGF',&*$)F&\"\"#F,F-*&)F*\"\"$F,F0F'F',&*&)F*F4F, )F0F4F,F'*$)F&F7F,F-,&*&)F0F7F,F*F,F'*$)F&F+F,F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%3Minimized~matrix:~G-%'matrixG6#7'7$\"\"\"\"\"!7$,$%\" zG!\"\"F)7$,&%\"xGF.*$)F-\"\"%\"\"\"F.*$)F-\"\"$F57$,(*&F7F5%\"yGF)F.* $)F1\"\"#F5F.*&F3F5F1F)F.,&*&)F-F?F5FF5F.,(*&FHF5F-F)F)*(F1F5FCF5FF5F7F5F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'mxbaseG7$7',&%\"x G!\"\"*$)%\"zG\"\"%\"\"\"\"\"\",&*&F,F/F(F/F/%\"yGF),&*$)F(\"\"#F.F)*& )F,\"\"$F.F2F/F/,&*&)F,F6F.)F2F6F.F/*$)F(F9F.F),&*&)F2F9F.F,F.F)*$)F(F -F.F/-%'matrixG6#7'7$F)\"\"!7$F,F)7$,&F(F)F*F)*$F8F.7$,(F7F)F4F)*&F+F. F(F.F),&*&FF/*&F+F.F5F. F/,(*&F=F.F,F.F)*(F(F.F " 0 "" {MPLTEXT 1 0 37 "base := matrix(2,1,[x-z^4, y - z^5]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%baseG-%'matrixG6#7$7#, &%\"xG\"\"\"*$)%\"zG\"\"%\"\"\"!\"\"7#,&%\"yGF,*$)F/\"\"&F1F2" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "simplify(multiply(mxbase[2], base));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7'7#,&%\"xG!\" \"*$)%\"zG\"\"%\"\"\"\"\"\"7#,&*&F-F0F)F0F0%\"yGF*7#,&*$)F)\"\"#F/F**& )F-\"\"$F/F4F0F07#,&*&)F-F9F/)F4F9F/F0*$)F)F " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 112 "Since this matrix gives the element of t he Groebner basis, the matrix given by mxgb() is what we claimed it wa s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 349 "As you may have noticed, there are quickbasis_mxgb, min_mxgb, and red_mx gb commands which have counterparts that do not have the \"mx\" prefix . All these commands are combined for the mxgb command, and are not m eant for users. This is not to say that you cannot use them, but thes e commands aren't terribly user friendly and we discourage their use. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 143 "That 's it for this tutorial. Remember, more information on these commands can be found below in the reference guide. Thank you and good luck! " }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 16 "Acknowledgements" }}{PARA 0 "" 0 "" {TEXT -1 117 "Will Gryc and David Cox would like to thank th e Charleton Trust for supporting Will's work on this Maple worksheet. \+ " }}}}{MARK "0" 0 }{VIEWOPTS 1 1 0 3 2 1804 }