1\section{Groebner package} 2\begin{Introduction}{Groebner bases} 3The GROEBNER package calculates \nameindex{Groebner bases} using the 4\nameindex{Buchberger algorithm} and provides related algorithms 5for arithmetic with ideal bases, such as ideal quotients, 6Hilbert polynomials (\nameindex{Hollmann algorithm}), 7basis conversion ( 8\nameindex{Faugere-Gianni-Lazard-Mora algorithm}), independent 9variable set (\nameindex{Kredel-Weispfenning algorithm}). 10 11 12 13Some routines of the Groebner package are used by \nameref{solve} - in 14that context the package is loaded automatically. However, if you 15want to use the package by explicit calls you must load it by 16\begin{verbatim} 17 load_package groebner; 18\end{verbatim} 19 20For the common parameter setting of most operators in this package 21see \nameref{ideal parameters}. 22\end{Introduction} 23 24 25 26\begin{Concept}{Ideal Parameters} 27\index{polynomial} 28Most operators of the \name{Groebner} package compute expressions in a 29polynomial ring which given as \meta{R}[\meta{var},\meta{var},...] where 30\meta{R} is the current REDUCE coefficient domain. All algebraically 31exact domains of REDUCE are supported. The package can operate over rings 32and fields. The operation mode is distinguished automatically. In 33general the ring mode is a bit faster than the field mode. The factoring 34variant can be applied only over domains which allow you factoring of 35multivariate polynomials. 36 37The variable sequence \meta{var} is either declared explicitly as argument 38in form of a \nameref{list} in \nameref{torder}, or it is extracted 39automatically from the expressions. In the second case the current REDUCE 40system order is used (see \nameref{korder}) for arranging the variables. 41If some kernels should play the role of formal parameters (the ground 42domain \meta{R} then is the polynomial ring over these), the variable 43sequences must be given explicitly. 44 45All REDUCE \nameref{kernel}s can be used as variables. But please note, 46that all variables are considered as independent. E.g. when using 47\name{sin(a)} and \name{cos(a)} as variables, the basic relation 48\name{sin(a)^2+cos(a)^2-1=0} must be explicitly added to an equation set 49because the Groebner operators don't include such knowledge automatically. 50 51The terms (monomials) in polynomials are arranged according to the current 52\nameref{term order}. Note that the algebraic properties of the computed 53results only are valid as long as neither the ordering nor the variable 54sequence changes. 55 56The input expressions \meta{exp} can be polynomials \meta{p}, rational 57functions \meta{n}/\meta{d} or equations \meta{lh}=\meta{rh} built from 58polynomials or rational functions. Apart from the \name{tracing} 59algorithms \nameref{groebnert} and \nameref{preducet}, where the equations 60have a specific meaning, equations are converted to simple expressions by 61taking the difference of the left-hand and right-hand sides 62\meta{lh}-\meta{rh}=>\meta{p}. Rational functions are converted to 63polynomials by converting the expression to a common denominator form 64first, and then using the numerator only \meta{n}=>\meta{p}. So eventual 65zeros of the denominators are ignored. 66 67A basis on input or output of an algorithm is coded as \nameref{list} of 68expressions \{\meta{exp},\meta{exp},...\} . \end{Concept} 69 70%----------------------------------------------------------------- 71\subsection{Term order} 72%----------------------------------------------------------------- 73\begin{Introduction}{Term order} 74\index{distributive polynomials} 75For all \name{Groebner} operations the polynomials are 76represented in distributive form: a sum of terms (monomials). 77The terms are ordered corresponding to the actual \name{term order} 78which is set by the \nameref{torder} operator, and to the 79actual variable sequence which is either given as explicit 80parameter or by the system \nameref{kernel} order. 81\end{Introduction} 82 83\begin{Operator}{torder} 84The operator \name{torder} sets the actual variable sequence and term order. 85 861. simple term order: 87\begin{Syntax} 88 \name{torder}\(\meta{vl}, \meta{m}\) 89\end{Syntax} 90 91where \meta{vl} is a \nameref{list} of variables (\nameref{kernel}s) and 92\meta{m} is the name of a simple \nameref{term order} mode 93\ref{lex term order}, \ref{gradlex term order}, 94\ref{revgradlex term order} or another implemented parameterless mode. 95 962. stepped term order: 97\begin{Syntax} 98 99 \name{torder} \(\meta{vl},\meta{m},\meta{n}\) 100 101\end{Syntax} 102 103where \meta{m} is the name of a two step term order, one of 104\nameref{gradlexgradlex term order}, \nameref{gradlexrevgradlex term order}, 105\nameref{lexgradlex term order} or \nameref{lexrevgradlex term order}, and 106\meta{n} is a positive integer. 107 1083. weighted term order 109\begin{Syntax} 110 \name{torder} \(\meta{vl}, \name{weighted}, \meta{n},\meta{n},...\); 111\end{Syntax} 112 113where the \meta{n} are positive integers, see \nameref{weighted term order}. 114 1154. matrix term order 116\begin{Syntax} 117 \name{torder} \(\meta{vl}, \name{matrix}, \meta{m}\); 118\end{Syntax} 119 120where \meta{m} is a matrix with integer elements, see 121\nameref{torder_compile}. 122 1235. compiled term order 124\begin{Syntax} 125 \name{torder} \(\meta{vl}, \name{co}\); 126\end{Syntax} 127 128where \meta{co} is the name of a routine generated by 129\nameref{torder_compile}. 130 131\name{torder} sets the variable sequence and the term order mode. If the 132an empty list is used as variable sequence, the automatic variable extraction 133is activated. The defaults are the empty variable list an the 134\nameref{lex term order}. 135The previous setting is returned as a list. 136 137Alternatively to the above syntax the arguments of \name{torder} may be 138collected in a \nameref{list} and passed as one argument to 139\name{torder}. 140 141\end{Operator} 142%------------------------------------------------------------ 143\begin{Operator}{torder_compile} 144\index{term order} 145A matrix can be converted into 146a compilable LISP program for faster execution by using 147\begin{Syntax} 148 \name{torder\_compile}\(\meta{name},\meta{mat}\) 149\end{Syntax} 150where \meta{name} is an identifier for the new term order and \meta{mat} 151is an integer matrix to be used as \nameref{matrix term order}. Afterwards 152the term order can be activated by using \meta{name} in a \nameref{torder} 153expression. The resulting program is compiled if the switch \nameref{comp} 154is on, or if the \name{torder\_compile} expression is part of a compiled 155module. 156\end{Operator} 157%------------------------------------------------------------ 158\begin{Concept}{lex term order} 159\index{term order}\index{variable elimination} 160The terms are ordered lexicographically: two terms t1 t2 161are compared for their degrees 162along the fixed variable sequence: t1 is higher than t2 163if the first different degree is higher in t1. 164This order has the \name{elimination property} 165for \name{groebner basis} calculations. 166If the ideal has a univariate polynomial in the last 167variable the groebner basis will contain 168such polynomial. \name{Lex} is best 169suited for solving of polynomial equation systems. 170 171\end{Concept} 172 173%------------------------------------------------------------ 174\begin{Concept}{gradlex term order} 175\index{term order} 176The terms are ordered first with their total 177degree, and if the total degree is identical 178the comparison is \nameref{lex term order}. 179With \name{groebner} basis calculations this term order 180produces polynomials of lowest degree. 181\end{Concept} 182 183%------------------------------------------------------------ 184\begin{Concept}{revgradlex term order} 185\index{term order} 186The terms are ordered first with their total 187degree (degree sum), and if the total degree is identical 188the comparison is the inverse of \nameref{lex term order}. 189With \nameref{groebner} and \nameref{groebnerf} 190calculations this term order 191is similar to \nameref{gradlex term order}; it is known 192as most efficient ordering with respect to computing time. 193\end{Concept} 194 195%------------------------------------------------------------ 196\begin{Concept}{gradlexgradlex term order} 197\index{term order} 198The terms are separated into two groups where the 199second parameter of the \nameref{torder} call determines 200the length of the first group. For a comparison first 201the total degrees of both variable groups are compared. 202If both are equal 203\nameref{gradlex term order} comparison is applied to the first 204group, and if that does not decide \nameref{gradlex term order} 205is applied for the second group. This order has the elimination 206property for the variable groups. It can be used e.g. for 207separating variables from parameters. 208\end{Concept} 209%------------------------------------------------------------ 210\begin{Concept}{gradlexrevgradlex term order} 211\index{term order} 212Similar to \nameref{gradlexgradlex term order}, but using 213\nameref{revgradlex term order} for the second group. 214\end{Concept} 215%------------------------------------------------------------ 216\begin{Concept}{lexgradlex term order} 217\index{term order} 218Similar to \nameref{gradlexgradlex term order}, but using 219\nameref{lex term order} for the first group. 220\end{Concept} 221%------------------------------------------------------------ 222\begin{Concept}{lexrevgradlex term order} 223\index{term order} 224Similar to \nameref{gradlexgradlex term order}, but using 225\nameref{lex term order} for the first group 226\nameref{revgradlex term order} for the second group. 227\end{Concept} 228%------------------------------------------------------------ 229\begin{Concept}{weighted term order} 230\index{term order} 231establishes a graduated ordering 232similar to \nameref{gradlex term order}, where the exponents first are 233multiplied by the given weights. If there are less weight values than 234variables, the weight list is extended by ones. If the weighted degree 235comparison is not decidable, the 236\nameref{lex term order} is used. 237\end{Concept} 238%------------------------------------------------------------ 239\begin{Concept}{graded term order} 240\index{term order} 241establishes a cascaded term ordering: first a graduated ordering 242similar to \nameref{gradlex term order} is used, where the exponents first are 243multiplied by the given weights. If there are less weight values than 244variables, the weight list is extended by ones. If the weighted degree 245comparison is not decidable, the term ordering described in the following 246parameters of the \nameref{torder} command is used. 247\end{Concept} 248%------------------------------------------------------------ 249\begin{Concept}{matrix term order} 250\index{term order} 251Any arbitrary term order mode can be installed by a matrix with 252integer elements where the row length corresponds to the variable 253number. The matrix must have at least as many rows as columns. 254It must have full rank, and the top nonzero element of each column 255must be positive. 256 257The matrix \name{term order mode} 258defines a term order where the exponent vectors of the monomials are 259first multiplied by the matrix and the resulting vectors are compared 260lexicographically. 261 262If the switch \nameref{comp} is on, the matrix is converted into 263a compiled LISP program for faster execution. A matrix can also be 264compiled explicitly, see \nameref{torder_compile}. 265\end{Concept} 266%--------------------------------------------------------------- 267%------------------------------------------------------------ 268\subsection{Basic Groebner operators} 269%------------------------------------------------------------- 270\begin{Operator}{gvars} 271\begin{Syntax} 272 273 \name{gvars}\(\{\meta{exp},\meta{exp},... \}\) 274 275\end{Syntax} 276 where \meta{exp} are expressions or \nameref{equation}s. 277 278\name{gvars} extracts from the expressions the \nameref{kernel}\name{s} 279which can 280play the role of variables for a \nameref{groebner} or \nameref{groebnerf} 281calculation. 282\end{Operator} 283 284%--------------------------------------------------------------- 285 286\begin{Operator}{groebner} 287\index{Buchberger algorithm} 288\begin{Syntax} 289 290 \name{groebner}\(\{\name{exp}, ...\}\) 291 292\end{Syntax} 293where \{\name{exp}, ... \} is a list of 294expressions or equations. 295 296 297The operator \name{groebner} implements the Buchberger algorithm 298for computing Groebner bases for a given set of 299expressions with respect to the given set of variables in the order 300given. As a side effect, the sequence of variables is stored as a REDUCE list 301in the shared variable \nameref{gvarslast} - this is important in cases 302where the algorithm rearranges the variable sequence because \nameref{groebopt} 303is \name{on}. 304 305\begin{Examples} 306 groebner({x**2+y**2-1,x-y}) & \{X - Y,2*Y**2 -1\} 307\end{Examples} 308\begin{Related} 309\item[ \nameref{groebnerf} operator] 310\item[ \nameref{gvarslast} variable] 311\item[ \nameref{groebopt} switch] 312\item[ \nameref{groebprereduce} switch] 313\item[ \nameref{groebfullreduction} switch] 314\item[ \nameref{gltbasis} switch] 315\item[ \nameref{gltb} variable] 316\item[ \nameref{glterms} variable] 317\item[ \nameref{groebstat} switch] 318\item[ \nameref{trgroeb} switch] 319\item[ \nameref{trgroebs} switch] 320\item[ \nameref{groebprot} switch] 321\item[ \nameref{groebprotfile} variable] 322\item[ \nameref{groebnert} operator] 323\end{Related} 324\end{Operator} 325%------------------------------------------------------- 326 327\begin{Operator}{groebner\_walk} 328The operator \name{groebner\_walk} computes a \nameref{lex} basis 329from a given \nameref{graded} (or \nameref{weighted}) one. 330\begin{Syntax} 331 \name{groebner\_walk}\(\meta{g}\) 332\end{Syntax} 333 334where \meta{g} is a \nameref{graded} basis (or \nameref{weighted} basis 335with a weight vector with one repeated element) of the polynomial ideal. 336\name{Groebner\_walk} computes a sequence of monomial bases, each 337time lifting the full system to a complete basis. \name{Groebner\_walk} 338should be called only in cases, where a normal \nameref{kex} computation 339would take too much computer time. 340 341The operator \nameref{torder} has to be called before in order to 342define the variable sequence and the term order mode of \meta{g}. 343 344The variable \nameref{gvarslast} is not set. 345 346Do not call \name{groebner\_walk} with \name{on} \nameref{groebopt}. 347 348\name{Groebner\_walk} includes some overhead (such as e. g. 349computation with division). On the other hand, sometimes 350\name{groebner\_walk} is faster than a direct \nameref{lex} computation. 351\end{Operator} 352 353%------------------------------------------------------- 354 355\begin{Switch}{groebopt} 356If \name{groebopt} is set ON, the sequence of variables is optimized 357with respect to execution speed of \name{groebner} calculations; 358note that the final list of variables is available in \nameref{gvarslast}. 359By default \name{groebopt} is off, conserving the original variable 360sequence. 361 362An explicitly declared dependency using the \nameref{depend} 363declaration supersedes the variable optimization. 364\begin{Examples} 365 366 depend a, x, y; 367 368\end{Examples} 369guarantees that a will be placed in front of x and y. 370\end{Switch} 371 372 373%------------------------------------------------------- 374 375\begin{Variable}{gvarslast} 376After a \nameref{groebner} or \nameref{groebnerf} calculation 377the actual variable sequence is stored in the variable 378\name{gvarslast}. If \nameref{groebopt} is \name{on} 379\name{gvarslast} shows the variable sequence after reordering. 380\end{Variable} 381 382%-------------------------------------------------------------- 383 384\begin{Switch}{groebprereduce} 385If \name{groebprereduce} set ON, \nameref{groebner} 386and \nameref{groebnerf} try to simplify the 387input expressions: if the head term of an input expression is a 388multiple of the head term of another expression, it can be reduced; 389these reductions are done cyclicly as long as possible in order to 390shorten the main part of the algorithm. 391 392By default \name{groebprereduce} is off. 393\end{Switch} 394 395%--------------------------------------------------------------- 396 397\begin{Switch}{groebfullreduction} 398If \name{groebfullreduction} set off, the polynomial reduction steps during 399\nameref{groebner} and \nameref{groebnerf} are limited to the pure head 400term reduction; subsequent terms are reduced otherwise. 401 402By default \name{groebfullreduction} is on. 403\end{Switch} 404 405%---------------------------------------------------------------- 406 407\begin{Switch}{gltbasis} 408If \name{gltbasis} set on, the leading terms of the result basis 409of a \nameref{groebner} or \nameref{groebnerf} calculation are 410extracted. They are collected as a basis of monomials, which is 411available as value of the global variable \nameref{gltb}. 412\end{Switch} 413%------------------------------------------------------------------ 414\begin{Variable}{gltb} 415See \nameref{gltbasis} 416\end{Variable} 417%------------------------------------------------------------------ 418 419\begin{Variable}{glterms} 420If the expressions in a \nameref{groebner} or \nameref{groebnerf} 421call contain parameters (symbols 422which are not member of the variable list), the share variable 423\name{glterms} is set to a list of expression which during the 424calculation were assumed to be nonzero. The calculated bases 425are valid only under the assumption that all these expressions do 426not vanish. 427\end{Variable} 428 429%----------------------------------------------------------- 430\begin{Switch}{groebstat} 431if \name{groebstat} is on, a summary of the 432\nameref{groebner} or \nameref{groebnerf} computation is printed 433at the end 434including the computing time, the number of intermediate 435H polynomials and the counters for the criteria hits. 436\end{Switch} 437 438%----------------------------------------------------------- 439\begin{Switch}{trgroeb} 440if \name{trgroeb} is on, intermediate H polynomials are 441printed during a \nameref{groebner} 442or \nameref{groebnerf} calculation. 443\end{Switch} 444 445%----------------------------------------------------------- 446\begin{Switch}{trgroebs} 447if \name{trgroebs} is on, intermediate H and S polynomials are 448printed during a \nameref{groebner} or \nameref{groebnerf} calculation. 449\end{Switch} 450 451%----------------------------------------------------------- 452\begin{Operator}{gzerodim?} 453\begin{Syntax} 454 455 \name{gzerodim!?}\(\meta{basis}\) 456 457\end{Syntax} 458where \meta{bas} is a Groebner basis in the current 459\nameref{term order} with the actual setting 460(see \nameref{ideal parameters}). 461 462 463\name{gzerodim!?} tests whether the ideal spanned by the given basis 464has dimension zero. If yes, the number of zeros is returned, 465\nameref{nil} otherwise. 466\end{Operator} 467 468%--------------------------------------------------------------- 469 470\begin{Operator}{gdimension} 471\index{ideal dimension}\index{groebner} 472\begin{Syntax} 473 474 \name{gdimension}\(\meta{bas}\) 475 476\end{Syntax} 477where \meta{bas} is a \nameref{groebner} basis in the current 478term order (see \nameref{ideal parameters}). 479\name{gdimension} computes the dimension of the ideal 480spanned by the given basis and returns the dimension as an integer 481number. The Kredel-Weispfenning algorithm is used: the dimension 482is the length of the longest independent variable set, 483see \nameref{gindependent\_sets} 484\end{Operator} 485 486 487%--------------------------------------------------------------- 488 489\begin{Operator}{gindependent\_sets} 490\index{ideal variables}\index{ideal dimension}\index{groebner} 491\index{Kredel-Weispfenning algorithm} 492\begin{Syntax} 493 494 \name{gindependent\_sets}\(\meta{bas}\) 495 496\end{Syntax} 497where \meta{bas} is a \nameref{groebner} basis in any \name{term order} 498(which must be the current \name{term order}) with the specified 499variables (see \nameref{ideal parameters}). 500 501 502\name{Gindependent_sets} computes the maximal 503left independent variable sets of the ideal, that are 504the variable sets which play the role of free parameters in the 505current ideal basis. Each set is a list which is a subset of the 506variable list. The result is a list of these sets. For an 507ideal with dimension zero the list is empty. 508The Kredel-Weispfenning algorithm is used. 509\end{Operator} 510 511%-------------------------------------------------------------- 512 513\begin{Operator}{dd_groebner} 514For a homogeneous system of polynomials under 515\nameref{graded term order}, \nameref{gradlex term order}, 516\nameref{revgradlex term order} 517or \nameref{weighted term order} 518a Groebner Base can be computed with limiting the grade 519of the intermediate S polynomials: 520\begin{Syntax} 521\name{dd_groebner}\(\meta{d1},\meta{d2},\meta{plist}\) 522\end{Syntax} 523where \meta{d1} is a non negative integer and \meta{d2} is an integer 524or ``infinity". A pair of polynomials is considered 525only if the grade of the lcm of their head terms is between 526\meta{d1} and \meta{d2}. 527For the term orders \name{graded} or \name{weighted} the (first) weight 528vector is used for the grade computation. Otherwise the total 529degree of a term is used. 530\end{Operator} 531 532%-------------------------------------------------------------- 533 534 535\begin{Operator}{glexconvert} 536\index{ideal variables}\index{term order} 537\begin{Syntax} 538 539\name{glexconvert}\(\meta{bas}[,\meta{vars}][,MAXDEG=\meta{mx}] 540[,NEWVARS=\meta{nv}]\) 541 542\end{Syntax} 543where \meta{bas} is a \nameref{groebner} basis 544in the current term order, \meta{mx} (optional) is a positive 545integer and \meta{nvl} (optional) is a list of variables 546(see \nameref{ideal parameters}). 547 548 549The operator \name{glexconvert} converts the basis 550of a zero-dimensional ideal (finite number 551of isolated solutions) from arbitrary ordering into a basis under 552\nameref{lex term order}. 553 554 555The parameter \meta{newvars} defines the new variable sequence. 556If omitted, the 557original variable sequence is used. If only a subset of variables is 558specified here, the partial ideal basis is evaluated. 559 560If \meta{newvars} is a list with one element, the minimal 561\nameindex{univariate polynomial} is computed. 562 563\meta{maxdeg} is an upper limit for the degrees. The algorithm stops with 564an error message, if this limit is reached. 565 566A warning occurs, if the ideal is not zero dimensional. 567\begin{Comments} 568During the call the \name{term order} of the input basis must 569be active. 570\end{Comments} 571\end{Operator} 572 573%-------------------------------------------------------------- 574 575\begin{Operator}{greduce} 576\begin{Syntax} 577 578\name{greduce}\(exp, \{exp1, exp2, \ldots , expm\}\) 579 580\end{Syntax} 581 582where exp is an expression, and \{exp1, exp2, ... , expm\} is 583a list of expressions or equations. 584 585 586\name{greduce} is functionally equivalent with a call to 587\nameref{groebner} and then a call to \nameref{preduce}. 588\end{Operator} 589 590%--------------------------------------------------------- 591 592\begin{Operator}{preduce} 593\begin{Syntax} 594 595 \name{preduce}\(\meta{p}, \{\meta{exp}, \ldots \}\) 596 597\end{Syntax} 598 599where \meta{p} is an expression, and \{\meta{exp}, ... \} is 600a list of expressions or equations. 601 602 603\name{Preduce} computes the remainder of \name{exp} 604modulo the given set of polynomials resp. equations. 605This result is unique (canonical) only if the given set 606is a \name{groebner} basis under the current \nameref{term order} 607 608see also: \nameref{preducet} operator. 609 610\end{Operator} 611 612 613%------------------------------------------- 614 615\begin{Operator}{idealquotient} 616\begin{Syntax} 617 618\name{idealquotient}\(\{\meta{exp}, ...\}, \meta{d}\) 619 620\end{Syntax} 621where \{\meta{exp},...\} is a list of 622expressions or equations, \meta{d} is a single expression or equation. 623 624 625\name{Idealquotient} computes the ideal quotient: 626ideal spanned by the expressions \{\meta{exp},...\} 627divided by the single polynomial/expression \meta{f}. The result 628is the \nameref{groebner} basis of the quotient ideal. 629\end{Operator} 630 631%------------------------------------------------------------- 632 633\begin{Operator}{hilbertpolynomial} 634\index{Hollmann algorithm} 635\begin{Syntax} 636 637 hilbertpolynomial\(\meta{bas}\) 638 639\end{Syntax} 640where \meta{bas} is a \nameref{groebner} basis in the 641current \nameref{term order}. 642 643The degree of the \name{Hilbert polynomial} is the 644dimension of the ideal spanned by the basis. For an 645ideal of dimension zero the Hilbert polynomial is a 646constant which is the number of common zeros of the 647ideal (including eventual multiplicities). 648The \name{Hollmann algorithm} is used. 649\end{Operator} 650 651%------------------------------------------- 652 653\begin{Operator}{saturation} 654\begin{Syntax} 655 656\name{saturation}\(\{\meta{exp}, ...\}, \meta{p}\) 657 658\end{Syntax} 659where \{\meta{exp},...\} is a list of 660expressions or equations, \meta{p} is a single polynomial. 661 662\name{Saturation} computes the quotient of the polynomial \meta{p} 663and a power (with unknown but finite exponent) of the ideal built from 664\{\meta{exp}, ...\}. The result is the computed quotient. \name{Saturation} 665calls \nameref{idealquotient} several times until the result does not change 666any more. 667\end{Operator} 668 669%------------------------------------------------------------- 670\subsection{Factorizing Groebner bases} 671%------------------------------------------------------------- 672 673\begin{Operator}{groebnerf} 674\begin{Syntax} 675 676\name{groebnerf}\(\{\meta{exp}, ...\}[,\{\},\{\meta{nz}, ... \}]\); 677 678\end{Syntax} 679where \{\meta{exp}, ... \} is a list of expressions or 680equations, and \{\meta{nz},... \} is 681an optional list of polynomials to be considered as non zero 682for this calculation. An empty list must be passed as second argument 683if the non-zero list is specified. 684 685 686\name{groebnerf} tries to separate polynomials into individual factors and 687to branch the computation in a recursive manner (factorization tree). 688The result is a list of partial Groebner bases. 689Multiplicities (one factor with a higher power, the same partial basis 690twice) are deleted as early as possible in order to speed up the 691calculation. 692 693The third parameter of \name{groebnerf} declares some polynomials 694nonzero. If any of these is found in a branch of the calculation 695the branch is canceled. 696 697\begin{Bigexample} 698groebnerf({ 3*x**2*y+2*x*y+y+9*x**2+5*x = 3, 699 2*x**3*y-x*y-y+6*x**3-2*x**2-3*x = -3, 700 x**3*y+x**2*y+3*x**3+2*x**2 }, {y,x}); 701 702 {{Y - 3,X}, 703 704 2 705 {2*Y + 2*X - 1,2*X - 5*X - 5}} 706\end{Bigexample} 707 708\begin{Related} 709\item[ \nameref{groebresmax} variable] 710\item[ \nameref{groebmonfac} variable] 711\item[ \nameref{groebrestriction} variable] 712\item[ \nameref{groebner} operator] 713\item[ \nameref{gvarslast} variable] 714\item[ \nameref{groebopt} switch] 715\item[ \nameref{groebprereduce} switch] 716\item[ \nameref{groebfullreduction} switch] 717\item[ \nameref{gltbasis} switch] 718\item[ \nameref{gltb} variable] 719\item[ \nameref{glterms} variable] 720\item[ \nameref{groebstat} switch] 721\item[ \nameref{trgroeb} switch] 722\item[ \nameref{trgroebs} switch] 723\item[ \nameref{groebnert} operator] 724\end{Related} 725 726\end{Operator} 727 728% ------------------------------------------------------------------ 729 730\begin{Variable}{groebmonfac} 731The variable \name{groebmonfac} is connected to 732the handling of monomial factors. A monomial factor is a product 733of variable powers as a factor, e.g. x**2*y in x**3*y - 7342*x**2*y**2. A monomial factor represents a solution of the type 735 x = 0 or y = 0 with a certain multiplicity. With 736\nameref{groebnerf} the multiplicity of monomial factors is lowered 737to the value of the shared variable \name{groebmonfac} 738which by default is 1 (= monomial factors remain present, but their 739multiplicity is brought down). With 740\name{groebmonfac}:= 0 741the monomial factors are suppressed completely. 742\end{Variable} 743 744% ---------------------------------------------------------------- 745\begin{Variable}{groebresmax} 746The variable \name{groebresmax} 747controls during \nameref{groebnerf} calculations 748the number of partial results. Its default value is 300. If 749more partial results are calculated, the calculation is 750terminated. 751\end{Variable} 752 753% ---------------------------------------------------------------- 754\begin{Variable}{groebrestriction} 755During \nameref{groebnerf} calculations 756irrelevant branches can be excluded 757by setting the variable \name{groebrestriction}. The 758following restrictions are implemented: 759\begin{Syntax} 760 \name{groebrestriction} := \name{nonnegative} \\ 761 \name{groebrestriction} := \name{positive}\\ 762 \name{groebrestriction} := \name{zeropoint} 763\end{Syntax} 764With \name{nonnegative} branches are excluded where one 765polynomial has no nonnegative real zeros; with \name{positive} 766the restriction is sharpened to positive zeros only. 767The restriction \name{zeropoint} excludes all branches 768which do not have the origin (0,0,...0) in their solution 769set. 770\end{Variable} 771 772%--------------------------------------------------------- 773\subsection{Tracing Groebner bases} 774%--------------------------------------------------------- 775\index{tracing Groebner} 776\begin{Switch}{groebprot} 777If \name{groebprot} is \name{ON} the computation steps during 778\nameref{preduce}, \nameref{greduce} and \nameref{groebner} 779are collected in a list which is assigned to the variable 780\nameref{groebprotfile}. 781\end{Switch} 782%---------------------------------------------------------- 783\begin{Variable}{groebprotfile} 784See \nameref{groebprot} switch. 785\end{Variable} 786%---------------------------------------------------------- 787 788\begin{Operator}{groebnert} 789\begin{Syntax} 790 791 \name{groebnert}\(\{\meta{v}=\meta{exp},...\}\) 792 793\end{Syntax} 794where \meta{v} are \nameref{kernel}\name{s} (simple or indexed variables), 795\meta{exp} are polynomials. 796 797 798\name{groebnert} is functionally equivalent to a \nameref{groebner} 799call for \{\meta{exp},...\}, but the result is a set of 800equations where the left-hand sides are the basis elements while 801the right-hand sides are the same values expressed as combinations 802of the input formulas, expressed in terms of the names \meta{v} 803\begin{Bigexample} 804 groebnert({p1=2*x**2+4*y**2-100,p2=2*x-y+1}); 805 806 GB1 := {2*X - Y + 1=P2, 807 808 2 809 9*Y - 2*Y - 199= - 2*X*P2 - Y*P2 + 2*P1 + P2} 810\end{Bigexample} 811\end{Operator} 812%---------------------------------------------------------- 813 814\begin{Operator}{preducet} 815\begin{Syntax} 816 817\name{preduce}\(\meta{p},\{\meta{v}=\meta{exp}...\}\) 818\end{Syntax} 819where \meta{p} is an expression, \meta{v} are kernels 820(simple or indexed variables), 821\name{exp} are polynomials. 822 823\name{preducet} computes the remainder of \meta{p} modulo \{\meta{exp},...\} 824similar to \nameref{preduce}, but the result is an equation 825which expresses the remainder as combination of the polynomials. 826\begin{Bigexample} 827 828 GB2 := {G1=2*X - Y + 1,G2=9*Y**2 - 2*Y - 199} 829 preducet(q=x**2,gb2); 830 831 - 16*Y + 208= - 18*X*G1 - 9*Y*G1 + 36*Q + 9*G1 - G2 832\end{Bigexample} 833\end{Operator} 834 835%------------------------------------------------------------ 836\subsection{Groebner Bases for Modules} 837%------------------------------------------------------------ 838\begin{Concept}{Module} 839Given a polynomial ring, e.g. R=Z[x,y,...] and an integer n>1. 840The vectors with n elements of R form a free MODULE under 841elementwise addition and multiplication with elements of R. 842 843For a submodule given by a finite basis a Groebner basis 844can be computed, and the facilities of the GROEBNER package 845are available except the operators \nameref{groebnerf} 846and \name{groesolve}. The vectors are encoded using auxiliary 847variables which represent the unit vectors in the module. 848These are declared in the share variable \nameref{gmodule}. 849 850\end{Concept} 851 852\begin{Variable}{gmodule} 853The vectors of a free \nameref{module} over a polynomial ring R 854are encoded as linear combinations with unit vectors of 855M which are represented by auxiliary variables. These 856must be collected in the variable \name{gmodule} before 857any call to an operator of the Groebner package. 858 859\begin{verbatim} 860 torder({x,y,v1,v2,v3})$ 861 gmodule := {v1,v2,v3}$ 862 g:=groebner({x^2*v1 + y*v2,x*y*v1 - v3,2y*v1 + y*v3}); 863\end{verbatim} 864 865compute the Groebner basis of the submodule 866 867\begin{verbatim} 868 ([x^2,y,0],[xy,0,-1],[0,2y,y]) 869\end{verbatim} 870The members of the list \name{gmodule} are automatically 871appended to the end of the variable list, if they are not 872yet members there. They take part in the actual term ordering. 873\end{Variable} 874 875%------------------------------------------------------------ 876\subsection{Computing with distributive polynomials} 877%------------------------------------------------------------ 878 879\begin{Operator}{gsort} 880\index{distributive polynomials} 881\begin{Syntax} 882 883 \name{gsort}\(\meta{p}\) 884\end{Syntax} 885where \meta{p} is a polynomial or a list of polynomials. 886 887The polynomials are reordered and sorted corresponding to 888the current \nameref{term order}. 889\begin{Examples} 890 891 torder lex;\\ 892 gsort(x**2+2x*y+y**2,{y,x}); & {y**2+2y*x+x**2} 893 894\end{Examples} 895\end{Operator} 896 897%------------------------------------------------------------ 898 899\begin{Operator}{gsplit} 900\index{distributive polynomials} 901\begin{Syntax} 902 903 \name{gsplit}\(\meta{p}[,\meta{vars}]\); 904\end{Syntax} 905where \meta{p} is a polynomial or a list of polynomials. 906 907The polynomial is reordered corresponding to the 908the current \nameref{term order} and then 909separated into leading term and reductum. Result is 910a list with the leading term as first and the reductum 911as second element. 912\begin{Examples} 913 914 torder lex;\\ 915 gsplit(x**2+2x*y+y**2,{y,x}); & \{y**2,2y*x+x**2\} 916 917\end{Examples} 918\end{Operator} 919%------------------------------------------------------- 920 921\begin{Operator}{gspoly} 922\index{distributive polynomials} 923\begin{Syntax} 924 925 \name{gspoly}\(\meta{p1},\meta{p2}\); 926 927\end{Syntax} 928where \meta{p1} and \meta{p2} are polynomials. 929 930The \name{subtraction} polynomial of p1 and p2 is computed 931corresponding to the method of the Buchberger algorithm for 932computing \name{groebner bases}: p1 and p2 are multiplied 933with terms such that when subtracting them the leading terms 934cancel each other. 935\end{Operator} 936 937