\chapter{GROEBNER: A Gr\"obner basis package} \label{GROEBNER} \typeout{{GROEBNER: A Gr\"obner basis package}} {\footnotesize \begin{center} Herbert Melenk \& Winfried Neun \\ Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\ Takustra\"se 7 \\ D--14195 Berlin--Dahlem, Germany \\[0.05in] e--mail: melenk@zib.de \\[0.05in] and \\[0.05in] H.M. M\"oller \\ Fernuniversit\"at Hagen FB Math und Informatik\\ Postfach 940 \\ D--58084 Hagen, Germany\\[0.05in] e--mail: Michael.Moeller@fernuni-hagen.de \end{center} } \ttindex{GROEBNER} Gr\"obner bases are a valuable tool for solving problems in connection with multivariate polynomials, such as solving systems of algebraic equations and analysing polynomial ideals. \index{GROEBNER package}\index{Buchberger's Algorithm} The GROEBNER package calculates Gr\"obner bases using the Buchberger algorithm. It can be used over a variety of different coefficient domains, and for different variable and term orderings. \section{} \subsection{Term Ordering} \par In the theory of Gr\"obner bases, the terms of polynomials are considered as ordered. Several order modes are available in the current package, including the basic modes: \index{LEX ! term order}\index{GRADLEX ! term order} \index{REVGRADLEX ! term order} \begin{center} LEX, GRADLEX, REVGRADLEX \end{center} All orderings are based on an ordering among the variables. For each pair of variables $(a,b)$ an order relation must be defined, {\em e.g.\ } ``$ a\gg b $''. The greater sign $\gg$ does not represent a numerical relation among the variables; it can be interpreted only in terms of formula representation: ``$a$'' will be placed in front of ``$b$'' or ``$a$'' is more complicated than ``$b$''. The sequence of variables constitutes this order base. So the notion of \[ \{x1,x2,x3\} \] as a list of variables at the same time means \[ x1 \gg x2 \gg x3 \] with respect to the term order. If terms (products of powers of variables) are compared with LEX, that term is chosen which has a greater variable or a higher degree if the greatest variable is the first in both. With GRADLEX the sum of all exponents (the total degree) is compared first, and if that does not lead to a decision, the LEX method is taken for the final decision. The REVGRADLEX method also compares the total degree first, but afterward it uses the LEX method in the reverse direction; this is the method originally used by Buchberger. Note that the LEX ordering is identical to the standard \REDUCE{} kernel ordering, when KORDER is set explicitly to the sequence of variables. \index{default ! term order} LEX is the default term order mode in the GROEBNER package. \section{The Basic Operators} \subsection{Term Ordering Mode} \begin{description} \ttindex{TORDER} \item [{\it TORDER}]($vl$,$m$,$[p_1,p_2,\ldots]$); where $vl$ is a variable list (or the empty list if no variables are declared explicitly), $m$ is the name of a term ordering mode LEX, GRADLEX, REV\-GRAD\-LEX (or another implemented mode) and $[p_1,p_2,\ldots]$ are additional parameters for the term ordering mode (not needed for the basic modes). TORDER sets variable set and the term ordering mode. The default mode is LEX. The previous description is returned as a list with corresponding elements. Such a list can alternatively passed as sole argument to TORDER. If the variable list is empty or if the TORDER declaration is omitted, the automatic variable extraction is activated. \ttindex{GVARS} \item[{\it GVARS}] ({\it\{exp$1$, exp$2$, $ \ldots$, exp$n$\}}); where $\{exp1, exp2, \ldots , expn\}$ is a list of expressions or equations. GVARS extracts from the expressions $\{exp1, exp2, \ldots , expn\}$ the kernels, which can play the role of variables for a Gr\"obner calculation. This can be used {\em e.g.\ } in a TORDER declaration. \end{description} \subsection{GROEBNER: Calculation of a Gr\"obner Basis} \begin{description} \ttindex{GROEBNER} \item[{\it GROEBNER}] $\{exp1, exp2, \ldots , expm\}; $ where $\{exp1, exp2, \ldots , expm\}$ is a list of expressions or equations. GROEBNER calculates the Gr\"obner basis of the given set of expressions with respect to the current TORDER setting. The Gr\"obner basis $\{1\}$ means that the ideal generated by the input polynomials is the whole polynomial ring, or equivalently, that the input polynomials have no zeros in common. As a side effect, the sequence of variables is stored as a \REDUCE\ list in the shared variable \ttindex{gvarslast}{\tt gvarslast}. \end{description} \example \index{GROEBNER package ! example} \begin{verbatim} torder({},lex)$ groebner{3*x**2*y + 2*x*y + y + 9*x**2 + 5*x - 3, 2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x + 3, x**3*y + x**2*y + 3*x**3 + 2*x**2 }; 2 {8*X - 2*Y + 5*Y + 3, 3 2 2*Y - 3*Y - 16*Y + 21} \end{verbatim} The operation of GROEBNER can be controlled by the following switches: \begin{description} \ttindex{GROEBOPT} \item[GROEBOPT] -- If set ON, the sequence of variables is optimized with respect to execution speed; note that the final list of variables is available in\ttindex{GVARSLAST} GVARSLAST. An explicitly declared dependency supersedes the variable optimization. By default GROEBOPT is off, conserving the original variable sequence. \ttindex{GROEBFULLREDUCTION} \item[GROEBFULLREDUCTION] -- If set off, the reduction steps during the \linebreak[4] GROEBNER operation are limited to the pure head term reduction; subsequent terms are reduced otherwise. By default GROEBFULLREDUCTION is on. \ttindex{GLTBASIS} \item[GLTBASIS] -- If set on, the leading terms of the result basis are extracted. They are collected in a basis of monomials, which is available as value of the global variable with the name GLTB. \end{description} \subsection{GZERODIM?: Test of $\dim = 0$} \begin{description} \ttindex{GZERODIM?} \item[{\it GZERODIM}!?] $bas$ \\ where {\it bas} is a Gr\"obner basis in the current setting. The result is {\it NIL}, if {\it bas} is the basis of an ideal of polynomials with more than finitely many common zeros. If the ideal is zero dimensional, {\em i.e.\ } the polynomials of the ideal have only finitely many zeros in common, the result is an integer $k$ which is the number of these common zeros (counted with multiplicities). \end{description} \subsection{GDIMENSION, GINDEPENDENT\_SETS} The following operators can be used to compute the dimension and the independent variable sets of an ideal which has the Gr\"obner basis {\it bas} with arbitrary term order: \begin{description} \ttindex{GDIMENSION}\ttindex{GINDEPENDENT\_SETS} \ttindex{ideal dimension}\ttindex{independent sets} \item[Gdimension]$bas$ \item[Gindependent\_sets]$bas$ {\it Gindependent\_sets} computes the maximal left independent variable sets of the ideal, that are the variable sets which play the role of free parameters in the current ideal basis. Each set is a list which is a subset of the variable list. The result is a list of these sets. For an ideal with dimension zero the list is empty. {\it GDimension} computes the dimension of the ideal, which is the maximum length of the independent sets. \end{description} \subsection{GLEXCONVERT: Conversion to a Lexical Base} \begin{description} \ttindex{GLEXCONVERT} \item[{\it GLEXCONVERT}] $ \left(\{exp,\ldots , expm\} \left[,\{var1 \ldots , varn\}\right]\right.$ \\ $\left. \left[,MAXDEG=mx\right] \left[,NEWVARS=\{nv1, \ldots , nvk\}\right]\right) $ \\ where $\{exp1, \ldots , expm\}$ is a Gr\"obner basis with $\{var1, \ldots , varn\}$ as variables in the current term order mode, $mx$ is an integer, and $\{nv1, \ldots , nvk\}$ is a subset of the basis variables. For this operator the source and target variable sets must be specified explicitly. \end{description} GLEXCONVERT converts a basis of a zero-dimensional ideal (finite number of isolated solutions) from arbitrary ordering into a basis under {\it lex} ordering. During the call of GLEXCONVERT the original ordering of the input basis must be still active. NEWVARS defines the new variable sequence. If omitted, the original variable sequence is used. If only a subset of variables is specified here, the partial ideal basis is evaluated. For the calculation of a univariate polynomial, NEW\-VARS should be a list with one element. MAXDEG is an upper limit for the degrees. The algorithm stops with an error message, if this limit is reached. A warning occurs if the ideal is not zero dimensional. GLEXCONVERT is an implementation of the FLGM algorithm. Often, the calculation of a Gr\"obner basis with a graded ordering and subsequent conversion to {\it lex} is faster than a direct {\it lex} calculation. Additionally, GLEXCONVERT can be used to transform a {\it lex} basis into one with different variable sequence, and it supports the calculation of a univariate polynomial. If the latter exists, the algorithm is even applicable in the non zero-dimensional case, if such a polynomial exists. \begin{verbatim} torder({{w,p,z,t,s,b},gradlex) g := groebner { f1 := 45*p + 35*s -165*b -36, 35*p + 40*z + 25*t - 27*s, 15*w + 25*p*s +30*z -18*t -165*b**2, -9*w + 15*p*t + 20*z*s, w*p + 2*z*t - 11*b**3, 99*w - 11*s*b +3*b**2, b**2 + 33/50*b + 2673/10000}; G := {60000*W + 9500*B + 3969, 1800*P - 3100*B - 1377, 18000*Z + 24500*B + 10287, 750*T - 1850*B + 81, 200*S - 500*B - 9, 2 10000*B + 6600*B + 2673} glexconvert(g,{w,p,z,t,s,b},maxdeg=5,newvars={w}); 2 100000000*W + 2780000*W + 416421 glexconvert(g,{w,p,z,t,s,b},maxdeg=5,newvars={p}); 2 6000*P - 2360*P + 3051 \end{verbatim} \subsection{GROEBNERF: Factorizing Gr\"obner Bases} If Gr\"obner bases are computed in order to solve systems of equations or to find the common roots of systems of polynomials, the factorizing version of the Buchberger algorithm can be used. The theoretical background is simple: if a polynomial $p$ can be represented as a product of two (or more) polynomials, {\em e.g.\ } $h= f*g$, then $h$ vanishes if and only if one of the factors vanishes. So if during the calculation of a Gr\"obner basis $h$ of the above form is detected, the whole problem can be split into two (or more) disjoint branches. Each of the branches is simpler than the complete problem; this saves computing time and space. The result of this type of computation is a list of (partial) Gr\"obner bases; the solution set of the original problem is the union of the solutions of the partial problems, ignoring the multiplicity of an individual solution. If a branch results in a basis $\{1\}$, then there is no common zero, {\em i.e.\ }no additional solution for the original problem, contributed by this branch. \subsubsection{GROEBNERF Call} \ttindex{GROEBNERF} The syntax of GROEBNERF is the same as for GROEBNER. \[ \mbox{\it GROEBNERF}(\{exp1, exp2, \ldots , expm\} [,\{\},\{nz1, \ldots nzk\}); \] where $\{exp1, exp2, \ldots , expm\} $ is a given list of expressions or equations, and $\{nz1, \ldots nzk\}$ is an optional list of polynomials known to be non-zero. GROEBNERF tries to separate polynomials into individual factors and to branch the computation in a recursive manner (factorisation tree). The result is a list of partial Gr\"obner bases. If no factorisation can be found or if all branches but one lead to the trivial basis $\{1\}$, the result has only one basis; nevertheless it is a list of lists of polynomials. If no solution is found, the result will be $\{\{1\}\}$. Multiplicities (one factor with a higher power, the same partial basis twice) are deleted as early as possible in order to speed up the calculation. The factorising is controlled by some switches. As a side effect, the sequence of variables is stored as a \REDUCE\ list in the shared variable \begin{center} gvarslast . \end{center} If GLTBASIS is on, a corresponding list of leading term bases is also produced and is available in the variable GLTB. The third parameter of GROEBNERF allows one to declare some polynomials nonzero. If any of these is found in a branch of the calculation the branch is cancelled. This can be used to save a substantial amount of computing time. The second parameter must be included as an empty list if the third parameter is to be used. \begin{verbatim} torder({x,y},lex)$ groebnerf { 3*x**2*y + 2*x*y + y + 9*x**2 + 5*x = 3, 2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x = -3, x**3*y + x**2*y + 3*x**3 + 2*x**2 }; {{Y - 3,X}, 2 {2*Y + 2*X - 1,2*X - 5*X - 5}} \end{verbatim} %} It is obvious here that the solutions of the equations can be read off immediately. All switches from GROEBNER are valid for GROEBNERF as well: \ttindex{GROEBOPT} \ttindex{GLTBASIS} \ttindex{GROEBFULLREDUCTION}\ttindex{GROEBSTAT}\ttindex{TRGROEB} \ttindex{TRGROEBS}\ttindex{TRGROEB1} \begin{center} \begin{tabular}{l} GROEBOPT \\ GLTBASIS \\ GROEBFULLREDUCTION \\ GROEBSTAT \\ TRGROEB \\ TRGROEBS \\ TRGROEB1 \end{tabular} \end{center} \subsubsection{Restriction of the Solution Space} In some applications only a subset of the complete solution set of a given set of equations is relevant, {\em e.g.\ } only nonnegative values or positive definite values for the variables. A significant amount of computing time can be saved if nonrelevant computation branches can be terminated early. Positivity: If a polynomial has no (strictly) positive zero, then every system containing it has no nonnegative or strictly positive solution. Therefore, the Buchberger algorithm tests the coefficients of the polynomials for equal sign if requested. For example, in $13*x + 15*y*z $ can be zero with real nonnegative values for $x, y$ and $z$ only if $x=0$ and $y=0$ or $ z=0$; this is a sort of ``factorization by restriction''. A polynomial $13*x + 15*y*z + 20$ never can vanish with nonnegative real variable values. Zero point: If any polynomial in an ideal has an absolute term, the ideal cannot have the origin point as a common solution. By setting the shared variable \ttindex{GROEBRESTRICTION} \begin{center} GROEBRESTRICTION \end{center} GROEBNERF is informed of the type of restriction the user wants to impose on the solutions: \begin{center} \begin{tabular}{l} {\it GROEBRESTRICTION:=NONEGATIVE;} \\ \hspace*{+.5cm} only nonnegative real solutions are of interest\vspace*{4mm} \\ {\it GROEBRESTRICTION:=POSITIVE;} \\ \hspace*{+.5cm}only nonnegative and nonzero solutions are of interest\vspace*{4mm} \\ {\it GROEBRESTRICTION:=ZEROPOINT;} \\ \hspace*{+.5cm}only solution sets which contain the point $\{0,0,\ldots,0\}$ are or interest. \end{tabular} \end{center} If GROEBNERF detects a polynomial which formally conflicts with the restriction, it either splits the calculation into separate branches, or, if a violation of the restriction is determined, it cancels the actual calculation branch. \subsection{GREDUCE, PREDUCE: Reduction of Polynomials} \subsubsection{Background} \label{GROEBNER:background} Reduction of a polynomial ``p'' modulo a given sets of polynomials ``B'' is done by the reduction algorithm incorporated in the Buchberger algorithm. % Subsection 3.5.2 \subsubsection{Reduction via Gr\"obner Basis Calculation} \ttindex{GREDUCE} \[ \mbox{\it GREDUCE}(exp, \{exp1, exp2, \ldots , expm\}]); \] where {\it exp} is an expression, and $\{exp1, exp2,\ldots , expm\}$ is a list of any number of expressions or equations. GREDUCE first converts the list of expressions $\{exp1, \ldots , expn\}$ to a Gr\"obner basis, and then reduces the given expression modulo that basis. An error results if the list of expressions is inconsistent. The returned value is an expression representing the reduced polynomial. As a side effect, GREDUCE sets the variable {\it gvarslast} in the same manner as GROEBNER does. \subsubsection{Reduction with Respect to Arbitrary Polynomials} \ttindex{PREDUCE} \[ PREDUCE(exp, \{exp1, exp2,\ldots , expm\}); \] where $ exp $ is an expression, and $\{exp1, exp2, \ldots , expm \}$ is a list of any number of expressions or equations. PREDUCE reduces the given expression modulo the set $\{exp1, \ldots , expm\}$. If this set is a Gr\"obner basis, the obtained reduced expression is uniquely determined. If not, then it depends on the subsequence of the single reduction steps (see~\ref{GROEBNER:background}). PREDUCE does not check whether $\{exp1, exp2, \ldots , expm\}$ is a Gr\"obner basis in the actual order. Therefore, if the expressions are a Gr\"obner basis calculated earlier with a variable sequence given explicitly or modified by optimisation, the proper variable sequence and term order must be activated first. \example (PREDUCE called with a Gr\"obner basis): \begin{verbatim} torder({x,y},lex); gb:=groebner{3*x**2*y + 2*x*y + y + 9*x**2 + 5*x - 3, 2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x + 3, x**3*y + x**2*y + 3*x**3 + 2*x**2}$ preduce (5*y**2 + 2*x**2*y + 5/2*x*y + 3/2*y + 8*x**2 + 3/2*x - 9/2, gb); 2 Y \end{verbatim} \section{Ideal Decomposition \& Equation System Solving} Based on the elementary Gr\"obner operations, the GROEBNER package offers additional operators, which allow the decomposition of an ideal or of a system of equations down to the individual solutions. Details of the operators\ttindex{GROESOLVE}\ttindex{GROEBNERF} \ttindex{IDEALQUOTIENT}GROESOLVE, GROEBNERF and IDEALQUOTIENT can be found in the full documentation, with associated functions.