@@ -1,1546 +1,1546 @@ -\documentstyle[11pt,reduce]{article} -\title{GROEBNER: A Package for Calculating Gr\"obner Bases} -\date{} -\author{ -H. Melenk \& W. Neun \\[0.05in] -Konrad--Zuse--Zentrum \\ -f\"ur Informationstechnik Berlin \\ -Heilbronner Strasse 10 \\ -D--10711 Berlin-Wilmersdorf \\ -Germany \\[0.05in] -Email: melenk@sc.zib--berlin.de \\[0.05in] -and \\[0.05in] -H.M. M\"oller \\[0.05in] -Fernuniversit\"at Hagen \\ -FB Math und Informatik\\ -Postfach 940 \\ -D--58084 Hagen \\ -Germany\\[0.05in] -Email: Michael.Moeller@fernuni-hagen.de} - -\begin{document} -\maketitle - -\index{Gr\"obner Bases} -Gr\"obner bases are a valuable tool for solving problems in -connection with multivariate polynomials, such as solving systems of -algebraic equations and analyzing polynomial ideals. For a definition -of Gr\"obner bases, a survey of possible applications and further -references, see~\cite{Buchberger:85}. Examples are given in \cite{Boege:86}, -in \cite{Buchberger:88} and also in the test file for this package. - -\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. - -The current version of the package uses parts of the previous -version, written by R. Gebauer, A.C. Hearn, H. Kredel and M. -M\"oller. The algorithms implemented in the current version are -documented in \cite{Faugere:89}, \cite{Gebauer:88}, -\cite{Kredel:88a} and \cite{Giovini:91}. - -\section{Compatibility} - -Important modifications of the present GROEBNER package compared -with the REDUCE 3.5 GROEBNER package: -\begin{itemize} -\item The variables of the polynomial ring are now declared in the - $TORDER$ statement together with the term order mode. The old - style (including the variable list in the function calls) - is still accepted, but will not be supported in future versions. -\item The term order mode $private$ has been eliminated. Instead the - mode $matrix$ has been introduced, which allows you to - define any compatible term order. For optimal efficiency - a matrix can be compiled. -\item Polynomial side relations in the parameter domain are now - considered inside the Gr\"obner calculations. You can enter - them as ordinary $LET$ rules. -\item There is an extension $NCPOLY$ for computing with - non--commutative ideals of solvable type. $NCPOLY$ is loaded - as a separate module, but it uses internally the functions - of $GROEBNER$. -\end{itemize} - -\section{Background} - -\subsection{Variables, Domains and Polynomials} - -The various functions of the GROEBNER package manipulate -equations and/or polynomials; equations are internally -transformed into polynomials by forming the difference of -left-hand side and right-hand side. - -All manipulations take place in a ring of polynomials in some -variables $x1, \ldots , xn$ over a coefficient domain $D$: -\[ -D [x1,\ldots , xn], -\] -where $D$ is a field or at least a ring without zero divisors. -The set of variables $x1,\ldots ,xn$ can be given explicitly by the -user or it is extracted automatically from the -input expressions. - -All REDUCE kernels can play the role of ``variables'' in this context; -examples are - -%{\small -\begin{verbatim} -X Y Z22 SIN(ALPHA) COS(ALPHA) C(1,2,3) C(1,3,2) FARINA4711 -\end{verbatim} -%} - -The domain $D$ is the current REDUCE domain with those kernels -adjoined that are not members of the list of variables. So the -elements of $D$ may be complicated polynomials themselves over -kernels not in the list of variables; if, however, the variables are -extracted automatically from the input expressions, $D$ is identical -with the current REDUCE domain. It is useful to regard kernels not -being members of the list of variables as ``parameters'', e.g. -\[ -\begin{array}{c} - a * x + (a - b) * y**2 \;\mbox{ with ``variables''}\ \{x,y\} \\ -\mbox{and ``parameters'' $\;a\;$ and $\;b\;$}\;. -\end{array} -\] - -The current version of the Buchberger algorithm has two internal -modes, a field mode and a ring mode. In the starting phase the -algorithm analyzes the domain type; if it recognizes $D$ as being a -ring it uses the ring mode, otherwise the field mode is needed. -Normally field calculations occur only if all coefficients are numbers -and if the current REDUCE domain is a field (e.g. rational numbers, -modular numbers). In general, the ring mode is faster. When no specific -REDUCE domain is selected, the ring mode is used, even if the input -formulas contain fractional coefficients: they are multiplied by their -common denominators so that they become integer polynomials. - - - -\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, 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. - -\example \ with $\{x,y,z\}$: \index{GROEBNER package ! example} -\[ -\begin{array}{rlll} -\multicolumn{2}{l}{\hspace*{-1cm}\mbox{\bf LEX:}}\\ - x * y **3 & \gg & y ** 48 & \mbox{(heavier variable)} \\ - x**4 * y**2 & \gg & x**3 * y**10 & \mbox{(higher degree in 1st -variable)} \vspace*{2mm} \\ -\multicolumn{2}{l}{\hspace*{-1cm}\mbox{\bf GRADLEX:}} \\ - y**3 * z**4 & \gg & x**3 * y**3 & \mbox{(higher total degree)} \\ - x*z & \gg & y**2 & \mbox{(equal total degree)} -\vspace*{2mm}\\ -\multicolumn{2}{l}{\hspace*{-1cm}\mbox{\bf -REVGRADLEX:}} \\ - y**3 * z**4 & \gg & x**3 * y**3 & \mbox{(higher total degree)} \\ - x*z & \ll & y**2 & \mbox{(equal total degree,} \\ - & & & \mbox{so reverse order of LEX)} -\end{array} -\] - -The formal description of the term order modes is similar to -\cite{Kredel:88}; this description regards only the exponents of a term, -which are written as vectors of integers with $0$ for exponents of a -variable which does not occur: -\[ -\begin{array}{l} - (e) = (e1,\ldots , en) \;\mbox{ representing }\; x1**e1 \ x2**e2 \cdots - xn**en. \\ - \deg(e) \; \mbox{ is the sum over all elements of } \;(e) \\ - (e) \gg (l) \Longleftrightarrow (e)-(l)\gg (0) = (0,\ldots ,0) -\end{array} -\] -\[ -\begin{array}{rll} -\multicolumn{1}{l}{\hspace*{-.5cm}\mbox{\bf LEX:}} \\ - (e) > lex > (0) & \Longrightarrow & e_k > 0 \mbox{ and } e_j =0 -\mbox{ for }\; j=1,\ldots , k-1\vspace*{2mm} \\ -\multicolumn{1}{l}{\hspace*{-.5cm}\mbox{\bf -GRADLEX:}} \\ - (e) >gl> (0) & \Longrightarrow & \deg(e)>0 \mbox { or } (e) >lex> -(0)\vspace*{2mm} \\ -\multicolumn{1}{l}{\hspace*{-.5cm}\mbox{\bf -REVGRADLEX:}}\\ - (e) >rgl> (0) & \Longrightarrow & \deg(e)>0 \mbox{ or }(e) 1$: the vectors with $n$ elements of $R$ -form a $module$ under vector addition (= componentwise addition) -and multiplication with elements of $R$. For a submodule -given by a finite basis a Gr\"obner basis -can be computed, and the facilities of the GROEBNER package -can be used except the operators $GROEBNERF$ and $GROESOLVE$. - -The vectors are encoded using auxiliary variables which represent -the unit vectors in the module. E.g. using ${v_1,v_2,v_3}$ the -module element $[x_1^2,0,x_1-x_2]$ is represented as -$x_1^2 v_1 + x_1 v_3 - x_2 v_3$. The use of ${v_1,v_2,v_3}$ -as unit vectors is set up by assigning the set of auxiliary variables -to the share variable $GMODULE$, e.g. -\begin{verbatim} - GMODULE := {V1,V2,V3}; -\end{verbatim} -After this declaration all monomials built from these variables -are considered as an algebraically independent basis of a vector -space. However, you had best use them only linearly. Once $GMODULE$ -has been set, the auxiliary variables automatically will be -added to the end of each variable list (if they are not yet -member there). -Example: -\begin{verbatim} - torder({x,y,v1,v2,v3},lex)$ - gmodule := {v1,v2,v3}$ - g:=groebner{x^2*v1 + y*v2,x*y*v1 - v3,2y*v1 + y*v3}; - - 2 -G := {X *V1 + Y*V2, - - 2 - X*V3 + Y *V2, - - 3 - Y *V2 - 2*V3, - - 2*Y*V1 + Y*V3} - - preduce((x+y)^3*v1,g); - - 1 3 2 - - X*Y*V2 - ---*Y *V3 - 3*Y *V2 + 3*Y*V3 - 2 - -\end{verbatim} - -In many cases a total degree oriented term order will be adequate -for computations in modules, e.g. for all cases where the -submodule membership is investigated. However, arranging -the auxiliary variables in an elimination oriented term order -can give interesting results. E.g. -\begin{verbatim} - p1:=(x-1)*(x^2-x+3)$ p2:=(x-1)*(x^2+x-5)$ - gmodule := {v1,v2,v3}; - torder({v1,x,v2,v3},lex)$ - gb:=groebner {p1*v1+v2,p2*v1+v3}; - -GB := {30*V1*X - 30*V1 + X*V2 - X*V3 + 5*V2 - 3*V3, - - 2 2 - X *V2 - X *V3 + X*V2 + X*V3 - 5*V2 - 3*V3} - - g:=coeffn(first gb,v1,1); - -G := 30*(X - 1) - - c1:=coeffn(first gb,v2,1); - -C1 := X + 5 - - c2:=coeffn(first gb,v3,1); - -C2 := - X - 3 - - c1*p1 + c2*p2; - -30*(X - 1) - -\end{verbatim} -Here two polynomials -are entered as vectors $[p_1,1,0]$ and $[p_2,0,1]$. Using a term -ordering such that the first dimension ranges highest and the -other components lowest, a classical cofactor computation is -executed just as in the extended Euclidean algorithm. -Consequently the leading polynomial in the resulting -basis shows the greatest common divisor of $p_1$ and $p_2$, -found as a coefficient of $v_1$ while the coefficients -of $v_2$ and $v_3$ are the cofactors $c_1$ and $c_2$ of the polynomials -$p_1$ and $p_2$ with the relation $gcd(p_1,p_2) = c_1p_1 + c_2p_2$. - - -\subsection{Additional Orderings} -Besides the basic orderings, there are ordering options that are used for -special purposes. - -\subsubsection{Separating the Variables into Groups } -\index{grouped ordering} -It is often desirable to separate variables -and formal parameters in a system of polynomials. -This can be done with a {\it lex} Gr\"obner -basis. That however may be hard to compute as it does more -separation than necessary. The following orderings group the -variables into two (or more) sets, where inside each set a classical -ordering acts, while the sets are handled via their total degrees, -which are compared in elimination style. So the Gr\"obner basis will -eliminate the members of the first set, if algebraically possible. -{\it Torder} here gets an additional parameter which describe the -grouping \ttindex{TORDER} -\begin{center}{\it -\begin{tabular}{l} -TORDER ($vl$,gradlexgradlex, $n$) \\ -TORDER ($vl$,gradlexrevgradlex,$n$) \\ -TORDER ($vl$,lexgradlex, $n$) \\ -TORDER ($vl$,lexrevgradlex, $n$) -\end{tabular}} -\end{center} -Here the integer $n$ is the number of variables in the first group -and the names combine the local ordering for the first and second -group, e.g. -\begin{center} -\begin{tabular}{llll} -\multicolumn{4}{l}{{\it lexgradlex}, 3 for $\{x_1,x_2,x_3,x_4,x_5\}$:} \\ -\multicolumn{4}{l}{$x_1^{i_1}\ldots x_5^{i_5} \gg x_1^{j_1}\ldots -x_5^{j_5}$} \\ -if & & & $(i_1,i_2,i_3) \gg_{lex}(j_1,j_2,j_3)$ \\ -& or & & $(i_1,i_2,i_3) = (j_1,j_2,j_3)$ \\ -& & and & $(i_4,i_5) \gg_{gradlex}(j_4,j_5)$ -\end{tabular} -\end{center} -Note that in the second place there is no {\it lex} ordering available; -that would not make sense. - -\subsubsection{Weighted Ordering} -\ttindex{TORDER} \index{weighted ordering} -The statement -\begin{center} -\begin{tabular}{cl} -{\it TORDER} &($vl$,weighted, $\{n_1,n_2,n_3 \ldots$\}) ; \\ -\end{tabular} -\end{center} -establishes a graduated ordering, where the exponents are first -multiplied by the given weights. If there are less weight values than -variables, the weight 1 is added automatically. If the weighted -degree calculation is not decidable, a $lex$ comparison follows. - -\subsubsection{Graded Ordering} -\ttindex{TORDER} \index{graded ordering} -The statement -\begin{center} -\begin{tabular}{cl} -{\it TORDER} &($vl$,graded, $\{n_1,n_2,n_3 \ldots\}$,$order_2$) ; \\ -\end{tabular} -\end{center} -establishes a graduated ordering, where the exponents are first -multiplied by the given weights. If there are less weight values than -variables, the weight 1 is added automatically. If the weighted -degree calculation is not decidable, the term order $order_2$ specified -in the following argument(s) is used. The ordering $graded$ is designed -primarily for use with the operator $dd\_groebner$. - - -\subsubsection{Matrix Ordering} -\ttindex{TORDER} \index{matrix ordering} -The statement -\begin{center} -\begin{tabular}{cl} -{\it TORDER} &($vl$,matrix, $M$) ; \\ -\end{tabular} -\end{center} -where $M$ is a matrix with integer elements and row length which -corresponds to the variable number. The exponents of each monomial -form a vector; two monomials are compared by multiplying their -exponent vectors first with $M$ and comparing the resulting vector -lexicographically. E.g. the unit matrix establishes the classical -$LEX$ term order mode, a matrix with a first row of ones followed -by the rows of a unit matrix corresponds to the $GRADLEX$ ordering. - -The matrix $M$ must have at least as many rows as columns; a non--square -matrix contains redundant rows. The matrix must have full rank, and -the top non--zero element of each column must be positive. - -The generality of the matrix based term order has its price: the -computing time spent in the term sorting is significantly higher -than with the specialized term orders. To overcome this problem, -you can compile a matrix term order -if your REDUCE is equipped with a LISP compiler; the -compilation reduces the computing time overhead significantly. -If you set the switch $COMP$ on, any new order matrix is compiled -when any operator of the GROEBNER package accesses it for the -first time. Alternatively you can compile a matrix explicitly -\begin{verbatim} - torder_compile(,); -\end{verbatim} -where $$ is a name (an identifier) and $$ is a term order matrix. -$torder\_compile$ transforms the matrix into a LISP program, which -is compiled by the LISP compiler when $COMP$ is on or when you -generate a fast loadable module. Later you can activate the new term -order by using the name $$ in a $torder$ statement as term ordering -mode. - -\subsection{Gr\"obner Bases for Graded Homogeneous Systems} - -For a homogeneous system of polynomials under a term order -{\it graded}, {\it gradlex}, {\it revgradlex} or {\it weighted} -a Gr\"obner Base can be computed with limiting the grade -of the intermediate $S$--polynomials: -\begin{description} -\ttindex{dd\_groebner} -\item [{\it dd\_groebner}]($d1$,$d2$,$\{p_1,p_2,\ldots\}$); -\end{description} -where $d1$ is a non--negative integer and $d2$ is an integer -$>$ $d1$ or ``infinity". A pair of polynomials is considered -only if the grade of the lcm of their head terms is between -$d1$ and $d2$. See \cite{BeWei:93} for the mathematical background. -For the term orders {\it graded} or {\it weighted} the (first) weight -vector is used for the grade computation. Otherwise the total -degree of a term is used. - -\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. -% Section 4.1 -\subsection{Solutions Based on Lex Type Gr\"obner Bases} -% Subsection 4.1.1 -\subsubsection{GROESOLVE: Solution of a Set of Polynomial Equations} -\ttindex{GROESOLVE} \ttindex{GROEBNERF} -The GROESOLVE operator incorporates a macro algorithm; -lexical Gr\"obner bases are computed by GROEBNERF and decomposed -into simpler ones by ideal decomposition techniques; if algebraically -possible, the problem is reduced to univariate polynomials which are -solved by SOLVE; if ROUNDED is on, numerical approximations are -computed for the roots of the univariate polynomials. -\[ - GROESOLVE(\{exp1, exp2, \ldots , expm\}[,\{var1, var2, \ldots , -varn\}]); \] -where $\{exp1, exp2,\ldots , expm\}$ is a list of any number of -expressions or equations, $\{var1, var2, \ldots , varn\}$ is an -optional list of variables. - -The result is a set of subsets. The subsets contain the solutions of the -polynomial equations. If there are only finitely many solutions, -then each subset is a set of expressions of triangular type -$\{exp1, exp2,\ldots , expn\},$ where $exp1$ depends only on -$var1,$ $exp2$ depends only on $var1$ and $var2$ etc. until $expn$ which -depends on $var1,\ldots,varn.$ This allows a successive determination of -the solution components. If there are infinitely many solutions, -some subsets consist in less than $n$ expressions. By considering some -of the variables as ``free parameters'', these subsets are usually -again of triangular type. - - -\example (intersections of a line with a circle): -\index{GROEBNER package ! example} - -\[ -GROESOLVE(\{x**2 - y**2 - a, p*x+q*y+s\},\{x,y\}); -\] -%{\small -\begin{verbatim} - 2 2 2 2 2 - {{X=(SQRT( - A*P + A*Q + S )*Q - P*S)/(P - Q ), - 2 2 2 2 2 - Y= - (SQRT( - A*P + A*Q + S )*P - Q*S)/(P - Q )}, - 2 2 2 2 2 - {X= - (SQRT( - A*P + A*Q + S )*Q + P*S)/(P - Q ), - 2 2 2 2 2 - Y=(SQRT( - A*P + A*Q + S )*P + Q*S)/(P - Q )}} -\end{verbatim} -%} -% Subsection 4.1.2 -\subsubsection{GROEPOSTPROC: Postprocessing of a Gr\"obner Basis} -\ttindex{GROEPOSTPROC} -In many cases, it is difficult to do the general Gr\"obner processing. -If a Gr\"obner basis with a {\it lex} ordering is calculated already (e.g., -by very individual parameter settings), the solutions can be derived -from it by a call to GROEPOSTPROC. GROESOLVE is functionally -equivalent to a call to GROEBNERF and subsequent calls to -GROEPOSTPROC for each partial basis. -\[ - GROEPOSTPROC(\{exp1, exp2, \ldots , expm\}[,\{var1, var2, \ldots , -varn\}]); -\] -where $\{exp1, exp2, \ldots , expm\}$ is a list of any number of -expressions, \linebreak[4] $\{var1, var2, \ldots ,$ $ varn\}$ is an -optional list of variables. The expressions must be a {\it lex} Gr\"obner -basis with the given variables; the ordering must be still active. - -The result is the same as with GROESOLVE. - -\begin{verbatim} -groepostproc({x3**2 + x3 + x2 - 1, - x2*x3 + x1*x3 + x3 + x1*x2 + x1 + 2, - x2**2 + 2*x2 - 1, - x1**2 - 2},{x3,x2,x1}); - -{{X3= - SQRT(2), - - X2=SQRT(2) - 1, - - X1=SQRT(2)}, - - {X3=SQRT(2), - - X2= - (SQRT(2) + 1), - - X1= - SQRT(2)}, - - SQRT(4*SQRT(2) + 9) - 1 - {X3=-------------------------, - 2 - - X2= - (SQRT(2) + 1), - - X1=SQRT(2)}, - - - (SQRT(4*SQRT(2) + 9) + 1) - {X3=------------------------------, - 2 - - X2= - (SQRT(2) + 1), - - X1=SQRT(2)}, - - SQRT( - 4*SQRT(2) + 9) - 1 - {X3=----------------------------, - 2 - - X2=SQRT(2) - 1, - - X1= - SQRT(2)}, - - - (SQRT( - 4*SQRT(2) + 9) + 1) - {X3=---------------------------------, - 2 - - X2=SQRT(2) - 1, - - X1= - SQRT(2)}} -\end{verbatim} - -% Subsection 4.1.3 -\subsubsection{IDEALQUOTIENT: Quotient of an Ideal and an Expression} -\ttindex{IDEALQUOTIENT} \index{ideal quotient} -Let $I$ be an ideal and $f$ be a polynomial in the same -variables. Then the algebraic quotient is defined by -\[ -I:f = \{ p \;| \; p * f \;\mbox{ member of }\; I\}\;. -\] -The ideal quotient $I:f$ contains $I$ and is obviously part of the -whole polynomial ring, i.e. contained in $\{1\}$. The case $I:f = -\{1\}$ is equivalent to $f$ being a member of $I$. The other extremal -case, $I:f=I$, occurs, when $f$ does not vanish at any general zero of $I$. -The explanation of the notion ``general zero'' introduced by van der -Waerden, however, is beyond the aim of this manual. The operation -of GROESOLVE/GROEPOSTPROC is based on nested ideal quotient -calculations. - -If $I$ is given by a basis and $f$ is given as an expression, the -quotient can be calculated by -\[ -IDEALQUOTIENT (\{exp1, \ldots , expm\}, exp); \] -where $\{exp1, exp2, \ldots , expm\}$ is a list of any number of -expressions or equations, {\it exp} is a single expression or equation. - -IDEALQUOTIENT calculates the algebraic quotient of the ideal $I$ -with the basis $\{exp1, exp2, \ldots , expm\}$ and {\it exp} with -respect to the variables given or extracted. $\{exp1, exp2, \ldots , -expm\}$ is not necessarily a Gr\"obner basis. -The result is the Gr\"obner basis of -the quotient. - -\subsection{Operators for Gr\"obner Bases in all Term Orderings} -\index{Hilbert polynomial} -In some cases where no Gr\"obner -basis with lexical ordering can be calculated, a calculation with a total -degree ordering is still possible. Then the Hilbert polynomial gives -information about the dimension of the solutions space and for finite -sets of solutions univariate polynomials can be calculated. The solutions -of the equation system then is contained in the cross product of all -solutions of all univariate polynomials. - -\subsubsection{HILBERTPOLYNOMIAL: Hilbert Polynomial of an Ideal} -\ttindex{HILBERTPOLYNOMIAL} -This algorithm was contributed by {\sc Joachim Hollman}, Royal -Institute of Technology, Stockholm (private communication). - -\[ -HILBERTPOLYNOMIAL (\{exp1, \ldots , expm\})\;; -\] -where $\{exp1, exp2, \ldots , expm\}$ is a list of any number of -expressions or equations. - -HILBERTPOLYNOMIAL calculates the Hilbert polynomial of the ideal -with basis $\{exp1, exp2, \ldots , expm\}$ with respect to the -variables given or extracted provided the given term ordering is -compatible with the degree, such as the GRADLEX- or REVGRADLEX-ordering. -The term ordering of the basis -must be active and $\{exp1, exp2,\ldots$, $ expm\}$ should be a -Gr\"obner basis with respect to this ordering. The Hilbert polynomial -gives information about the cardinality of solutions of the system -$\{exp1, exp2, \ldots , expm\}$: if the Hilbert polynomial is an -integer, the system has only a discrete set of solutions and the -polynomial is identical with the number of solutions counted with -their multiplicities. Otherwise the degree of the Hilbert -polynomial is the dimension of the solution space. - -If the Hilbert polynomial is not a constant, it is constructed with the -variable ``X'' regardless of whether $x$ is member of $\{var1, var2, -\ldots , varn\}$ or not. The value of this polynomial at sufficiently -large numbers ``X'' -is the difference -of the dimension of the linear vector space of all polynomials of degree -$ \leq X $ minus the dimension of the subspace of all polynomials of -degree $\leq X $ which belong also to the ideal. - -\paragraph{Remark:} The number of zeros in an ideal and the -Hilbert polynomial depend only on the leading terms of the -Gr\"obner basis. So if a subsequent Hilbert calculation is planned, the -Gr\"obner calculation should be performed with ON GLTBASIS and -the value of GLTB (or its elements in a GROEBNERF context) should be -given to HILBERTPOLYNOMIAL. In this manner, a lot of computing time can be -saved in the case of large bases. - -% Chapter 5. -\section{Calculations ``by Hand''} -The following operators support explicit calculations with -polynomials in a distributive representation at the REDUCE top level. -So they allow one to do Gr\"obner type evaluations stepwise by -separate calls. Note that the normal REDUCE arithmetic can be used -for arithmetic combinations of monomials and polynomials. - -% Subsection 5.1 -\subsection{Representing Polynomials in Distributive Form} -\ttindex{GSORT} -\[ - GSORT (p); -\] -where $p$ is a polynomial or a list of polynomials. - -If $p$ is a single polynomial, the result is a reordered version of $p$ -in the distributive representation according to the variables and the -current term order mode; if $p$ is a list, its members are converted -into distributive representation and the result is the list sorted by -the term ordering of the leading terms; zero polynomials are -eliminated from the result. - -\begin{verbatim} - torder({alpha,beta,gamma},lex); - dip := gsort(gamma*(alpha-1)**2*(beta+1)**2); - - - 2 2 2 - DIP := ALPHA *BETA *GAMMA + 2*ALPHA *BETA*GAMMA - - 2 2 - + ALPHA *GAMMA - 2*ALPHA*BETA *GAMMA - 4*ALPHA*BETA*GAMMA - - 2 - - 2*ALPHA*GAMMA + BETA *GAMMA + 2*BETA*GAMMA + GAMMA - - \end{verbatim} - - -% Subsection 5.2 -\subsection{Splitting of a Polynomial into Leading Term and Reductum} -\ttindex{GSPLIT} -\[ -GSPLIT (p); -\] -where $p$ is a polynomial. - -GSPLIT converts the polynomial $p$ into distributive representation -and splits it into leading monomial and reductum. The result is a list -with two elements, the leading monomial and the reductum. - -\begin{verbatim} - gslit(dip); - - 2 2 - {ALPHA *BETA *GAMMA, - - 2 2 2 - 2*ALPHA *BETA*GAMMA + ALPHA *GAMMA - 2*ALPHA*BETA *GAMMA - - 2 - - 4*ALPHA*BETA*GAMMA - 2*ALPHA*GAMMA + BETA *GAMMA - - - + 2*BETA*GAMMA + GAMMA} - - \end{verbatim} - - -\subsection{Calculation of Buchberger's S-polynomial} -\ttindex{GSPOLY} -\[ -GSPOLY (p1,p2); -\] -where $p1$ and $p2$ are polynomials. - -GSPOLY calculates the $S$-polynomial from $p1$ and $p2$; - -Example for a complete calculation (taken from {\sc Davenport et al.} - \cite{Davenport:88a}): -\begin{verbatim} - torder({x,y,z},lex)$ - g1 := x**3*y*z - x*z**2; - g2 := x*y**2*z - x*y*z; - g3 := x**2*y**2 - z;$ - - % first S-polynomial - - g4 := gspoly(g2,g3);$ - - 2 2 - G4 := X *Y*Z - Z - - % next S-polynomial - - p := gspoly(g2,g4); $ - - 2 2 - P := X *Y*Z - Y*Z - - % and reducing, here only by g4 - - g5 := preduce(p,{g4}); - - 2 2 - G5 := - Y*Z + Z - - % last S-polynomial} - - g6 := gspoly(g4,g5); - - 2 2 3 - G6 := X *Z - Z - - % and the final basis sorted descending - - gsort{g2,g3,g4,g5,g6}; - - 2 2 - {X *Y - Z, - - 2 2 - X *Y*Z - Z , - - 2 2 3 - X *Z - Z , - - 2 - X*Y *Z - X*Y*Z, - - 2 2 - - Y*Z + Z } - \end{verbatim} - -\bibliography{groebner} -\bibliographystyle{plain} -\end{document} - +\documentstyle[11pt,reduce]{article} +\title{GROEBNER: A Package for Calculating Gr\"obner Bases} +\date{} +\author{ +H. Melenk \& W. Neun \\[0.05in] +Konrad--Zuse--Zentrum \\ +f\"ur Informationstechnik Berlin \\ +Heilbronner Strasse 10 \\ +D--10711 Berlin-Wilmersdorf \\ +Germany \\[0.05in] +Email: melenk@sc.zib--berlin.de \\[0.05in] +and \\[0.05in] +H.M. M\"oller \\[0.05in] +Fernuniversit\"at Hagen \\ +FB Math und Informatik\\ +Postfach 940 \\ +D--58084 Hagen \\ +Germany\\[0.05in] +Email: Michael.Moeller@fernuni-hagen.de} + +\begin{document} +\maketitle + +\index{Gr\"obner Bases} +Gr\"obner bases are a valuable tool for solving problems in +connection with multivariate polynomials, such as solving systems of +algebraic equations and analyzing polynomial ideals. For a definition +of Gr\"obner bases, a survey of possible applications and further +references, see~\cite{Buchberger:85}. Examples are given in \cite{Boege:86}, +in \cite{Buchberger:88} and also in the test file for this package. + +\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. + +The current version of the package uses parts of the previous +version, written by R. Gebauer, A.C. Hearn, H. Kredel and M. +M\"oller. The algorithms implemented in the current version are +documented in \cite{Faugere:89}, \cite{Gebauer:88}, +\cite{Kredel:88a} and \cite{Giovini:91}. + +\section{Compatibility} + +Important modifications of the present GROEBNER package compared +with the REDUCE 3.5 GROEBNER package: +\begin{itemize} +\item The variables of the polynomial ring are now declared in the + $TORDER$ statement together with the term order mode. The old + style (including the variable list in the function calls) + is still accepted, but will not be supported in future versions. +\item The term order mode $private$ has been eliminated. Instead the + mode $matrix$ has been introduced, which allows you to + define any compatible term order. For optimal efficiency + a matrix can be compiled. +\item Polynomial side relations in the parameter domain are now + considered inside the Gr\"obner calculations. You can enter + them as ordinary $LET$ rules. +\item There is an extension $NCPOLY$ for computing with + non--commutative ideals of solvable type. $NCPOLY$ is loaded + as a separate module, but it uses internally the functions + of $GROEBNER$. +\end{itemize} + +\section{Background} + +\subsection{Variables, Domains and Polynomials} + +The various functions of the GROEBNER package manipulate +equations and/or polynomials; equations are internally +transformed into polynomials by forming the difference of +left-hand side and right-hand side. + +All manipulations take place in a ring of polynomials in some +variables $x1, \ldots , xn$ over a coefficient domain $D$: +\[ +D [x1,\ldots , xn], +\] +where $D$ is a field or at least a ring without zero divisors. +The set of variables $x1,\ldots ,xn$ can be given explicitly by the +user or it is extracted automatically from the +input expressions. + +All REDUCE kernels can play the role of ``variables'' in this context; +examples are + +%{\small +\begin{verbatim} +X Y Z22 SIN(ALPHA) COS(ALPHA) C(1,2,3) C(1,3,2) FARINA4711 +\end{verbatim} +%} + +The domain $D$ is the current REDUCE domain with those kernels +adjoined that are not members of the list of variables. So the +elements of $D$ may be complicated polynomials themselves over +kernels not in the list of variables; if, however, the variables are +extracted automatically from the input expressions, $D$ is identical +with the current REDUCE domain. It is useful to regard kernels not +being members of the list of variables as ``parameters'', e.g. +\[ +\begin{array}{c} + a * x + (a - b) * y**2 \;\mbox{ with ``variables''}\ \{x,y\} \\ +\mbox{and ``parameters'' $\;a\;$ and $\;b\;$}\;. +\end{array} +\] + +The current version of the Buchberger algorithm has two internal +modes, a field mode and a ring mode. In the starting phase the +algorithm analyzes the domain type; if it recognizes $D$ as being a +ring it uses the ring mode, otherwise the field mode is needed. +Normally field calculations occur only if all coefficients are numbers +and if the current REDUCE domain is a field (e.g. rational numbers, +modular numbers). In general, the ring mode is faster. When no specific +REDUCE domain is selected, the ring mode is used, even if the input +formulas contain fractional coefficients: they are multiplied by their +common denominators so that they become integer polynomials. + + + +\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, 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. + +\example \ with $\{x,y,z\}$: \index{GROEBNER package ! example} +\[ +\begin{array}{rlll} +\multicolumn{2}{l}{\hspace*{-1cm}\mbox{\bf LEX:}}\\ + x * y **3 & \gg & y ** 48 & \mbox{(heavier variable)} \\ + x**4 * y**2 & \gg & x**3 * y**10 & \mbox{(higher degree in 1st +variable)} \vspace*{2mm} \\ +\multicolumn{2}{l}{\hspace*{-1cm}\mbox{\bf GRADLEX:}} \\ + y**3 * z**4 & \gg & x**3 * y**3 & \mbox{(higher total degree)} \\ + x*z & \gg & y**2 & \mbox{(equal total degree)} +\vspace*{2mm}\\ +\multicolumn{2}{l}{\hspace*{-1cm}\mbox{\bf +REVGRADLEX:}} \\ + y**3 * z**4 & \gg & x**3 * y**3 & \mbox{(higher total degree)} \\ + x*z & \ll & y**2 & \mbox{(equal total degree,} \\ + & & & \mbox{so reverse order of LEX)} +\end{array} +\] + +The formal description of the term order modes is similar to +\cite{Kredel:88}; this description regards only the exponents of a term, +which are written as vectors of integers with $0$ for exponents of a +variable which does not occur: +\[ +\begin{array}{l} + (e) = (e1,\ldots , en) \;\mbox{ representing }\; x1**e1 \ x2**e2 \cdots + xn**en. \\ + \deg(e) \; \mbox{ is the sum over all elements of } \;(e) \\ + (e) \gg (l) \Longleftrightarrow (e)-(l)\gg (0) = (0,\ldots ,0) +\end{array} +\] +\[ +\begin{array}{rll} +\multicolumn{1}{l}{\hspace*{-.5cm}\mbox{\bf LEX:}} \\ + (e) > lex > (0) & \Longrightarrow & e_k > 0 \mbox{ and } e_j =0 +\mbox{ for }\; j=1,\ldots , k-1\vspace*{2mm} \\ +\multicolumn{1}{l}{\hspace*{-.5cm}\mbox{\bf +GRADLEX:}} \\ + (e) >gl> (0) & \Longrightarrow & \deg(e)>0 \mbox { or } (e) >lex> +(0)\vspace*{2mm} \\ +\multicolumn{1}{l}{\hspace*{-.5cm}\mbox{\bf +REVGRADLEX:}}\\ + (e) >rgl> (0) & \Longrightarrow & \deg(e)>0 \mbox{ or }(e) 1$: the vectors with $n$ elements of $R$ +form a $module$ under vector addition (= componentwise addition) +and multiplication with elements of $R$. For a submodule +given by a finite basis a Gr\"obner basis +can be computed, and the facilities of the GROEBNER package +can be used except the operators $GROEBNERF$ and $GROESOLVE$. + +The vectors are encoded using auxiliary variables which represent +the unit vectors in the module. E.g. using ${v_1,v_2,v_3}$ the +module element $[x_1^2,0,x_1-x_2]$ is represented as +$x_1^2 v_1 + x_1 v_3 - x_2 v_3$. The use of ${v_1,v_2,v_3}$ +as unit vectors is set up by assigning the set of auxiliary variables +to the share variable $GMODULE$, e.g. +\begin{verbatim} + GMODULE := {V1,V2,V3}; +\end{verbatim} +After this declaration all monomials built from these variables +are considered as an algebraically independent basis of a vector +space. However, you had best use them only linearly. Once $GMODULE$ +has been set, the auxiliary variables automatically will be +added to the end of each variable list (if they are not yet +member there). +Example: +\begin{verbatim} + torder({x,y,v1,v2,v3},lex)$ + gmodule := {v1,v2,v3}$ + g:=groebner{x^2*v1 + y*v2,x*y*v1 - v3,2y*v1 + y*v3}; + + 2 +G := {X *V1 + Y*V2, + + 2 + X*V3 + Y *V2, + + 3 + Y *V2 - 2*V3, + + 2*Y*V1 + Y*V3} + + preduce((x+y)^3*v1,g); + + 1 3 2 + - X*Y*V2 - ---*Y *V3 - 3*Y *V2 + 3*Y*V3 + 2 + +\end{verbatim} + +In many cases a total degree oriented term order will be adequate +for computations in modules, e.g. for all cases where the +submodule membership is investigated. However, arranging +the auxiliary variables in an elimination oriented term order +can give interesting results. E.g. +\begin{verbatim} + p1:=(x-1)*(x^2-x+3)$ p2:=(x-1)*(x^2+x-5)$ + gmodule := {v1,v2,v3}; + torder({v1,x,v2,v3},lex)$ + gb:=groebner {p1*v1+v2,p2*v1+v3}; + +GB := {30*V1*X - 30*V1 + X*V2 - X*V3 + 5*V2 - 3*V3, + + 2 2 + X *V2 - X *V3 + X*V2 + X*V3 - 5*V2 - 3*V3} + + g:=coeffn(first gb,v1,1); + +G := 30*(X - 1) + + c1:=coeffn(first gb,v2,1); + +C1 := X + 5 + + c2:=coeffn(first gb,v3,1); + +C2 := - X - 3 + + c1*p1 + c2*p2; + +30*(X - 1) + +\end{verbatim} +Here two polynomials +are entered as vectors $[p_1,1,0]$ and $[p_2,0,1]$. Using a term +ordering such that the first dimension ranges highest and the +other components lowest, a classical cofactor computation is +executed just as in the extended Euclidean algorithm. +Consequently the leading polynomial in the resulting +basis shows the greatest common divisor of $p_1$ and $p_2$, +found as a coefficient of $v_1$ while the coefficients +of $v_2$ and $v_3$ are the cofactors $c_1$ and $c_2$ of the polynomials +$p_1$ and $p_2$ with the relation $gcd(p_1,p_2) = c_1p_1 + c_2p_2$. + + +\subsection{Additional Orderings} +Besides the basic orderings, there are ordering options that are used for +special purposes. + +\subsubsection{Separating the Variables into Groups } +\index{grouped ordering} +It is often desirable to separate variables +and formal parameters in a system of polynomials. +This can be done with a {\it lex} Gr\"obner +basis. That however may be hard to compute as it does more +separation than necessary. The following orderings group the +variables into two (or more) sets, where inside each set a classical +ordering acts, while the sets are handled via their total degrees, +which are compared in elimination style. So the Gr\"obner basis will +eliminate the members of the first set, if algebraically possible. +{\it Torder} here gets an additional parameter which describe the +grouping \ttindex{TORDER} +\begin{center}{\it +\begin{tabular}{l} +TORDER ($vl$,gradlexgradlex, $n$) \\ +TORDER ($vl$,gradlexrevgradlex,$n$) \\ +TORDER ($vl$,lexgradlex, $n$) \\ +TORDER ($vl$,lexrevgradlex, $n$) +\end{tabular}} +\end{center} +Here the integer $n$ is the number of variables in the first group +and the names combine the local ordering for the first and second +group, e.g. +\begin{center} +\begin{tabular}{llll} +\multicolumn{4}{l}{{\it lexgradlex}, 3 for $\{x_1,x_2,x_3,x_4,x_5\}$:} \\ +\multicolumn{4}{l}{$x_1^{i_1}\ldots x_5^{i_5} \gg x_1^{j_1}\ldots +x_5^{j_5}$} \\ +if & & & $(i_1,i_2,i_3) \gg_{lex}(j_1,j_2,j_3)$ \\ +& or & & $(i_1,i_2,i_3) = (j_1,j_2,j_3)$ \\ +& & and & $(i_4,i_5) \gg_{gradlex}(j_4,j_5)$ +\end{tabular} +\end{center} +Note that in the second place there is no {\it lex} ordering available; +that would not make sense. + +\subsubsection{Weighted Ordering} +\ttindex{TORDER} \index{weighted ordering} +The statement +\begin{center} +\begin{tabular}{cl} +{\it TORDER} &($vl$,weighted, $\{n_1,n_2,n_3 \ldots$\}) ; \\ +\end{tabular} +\end{center} +establishes a graduated ordering, where the exponents are first +multiplied by the given weights. If there are less weight values than +variables, the weight 1 is added automatically. If the weighted +degree calculation is not decidable, a $lex$ comparison follows. + +\subsubsection{Graded Ordering} +\ttindex{TORDER} \index{graded ordering} +The statement +\begin{center} +\begin{tabular}{cl} +{\it TORDER} &($vl$,graded, $\{n_1,n_2,n_3 \ldots\}$,$order_2$) ; \\ +\end{tabular} +\end{center} +establishes a graduated ordering, where the exponents are first +multiplied by the given weights. If there are less weight values than +variables, the weight 1 is added automatically. If the weighted +degree calculation is not decidable, the term order $order_2$ specified +in the following argument(s) is used. The ordering $graded$ is designed +primarily for use with the operator $dd\_groebner$. + + +\subsubsection{Matrix Ordering} +\ttindex{TORDER} \index{matrix ordering} +The statement +\begin{center} +\begin{tabular}{cl} +{\it TORDER} &($vl$,matrix, $M$) ; \\ +\end{tabular} +\end{center} +where $M$ is a matrix with integer elements and row length which +corresponds to the variable number. The exponents of each monomial +form a vector; two monomials are compared by multiplying their +exponent vectors first with $M$ and comparing the resulting vector +lexicographically. E.g. the unit matrix establishes the classical +$LEX$ term order mode, a matrix with a first row of ones followed +by the rows of a unit matrix corresponds to the $GRADLEX$ ordering. + +The matrix $M$ must have at least as many rows as columns; a non--square +matrix contains redundant rows. The matrix must have full rank, and +the top non--zero element of each column must be positive. + +The generality of the matrix based term order has its price: the +computing time spent in the term sorting is significantly higher +than with the specialized term orders. To overcome this problem, +you can compile a matrix term order +if your REDUCE is equipped with a LISP compiler; the +compilation reduces the computing time overhead significantly. +If you set the switch $COMP$ on, any new order matrix is compiled +when any operator of the GROEBNER package accesses it for the +first time. Alternatively you can compile a matrix explicitly +\begin{verbatim} + torder_compile(,); +\end{verbatim} +where $$ is a name (an identifier) and $$ is a term order matrix. +$torder\_compile$ transforms the matrix into a LISP program, which +is compiled by the LISP compiler when $COMP$ is on or when you +generate a fast loadable module. Later you can activate the new term +order by using the name $$ in a $torder$ statement as term ordering +mode. + +\subsection{Gr\"obner Bases for Graded Homogeneous Systems} + +For a homogeneous system of polynomials under a term order +{\it graded}, {\it gradlex}, {\it revgradlex} or {\it weighted} +a Gr\"obner Base can be computed with limiting the grade +of the intermediate $S$--polynomials: +\begin{description} +\ttindex{dd\_groebner} +\item [{\it dd\_groebner}]($d1$,$d2$,$\{p_1,p_2,\ldots\}$); +\end{description} +where $d1$ is a non--negative integer and $d2$ is an integer +$>$ $d1$ or ``infinity". A pair of polynomials is considered +only if the grade of the lcm of their head terms is between +$d1$ and $d2$. See \cite{BeWei:93} for the mathematical background. +For the term orders {\it graded} or {\it weighted} the (first) weight +vector is used for the grade computation. Otherwise the total +degree of a term is used. + +\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. +% Section 4.1 +\subsection{Solutions Based on Lex Type Gr\"obner Bases} +% Subsection 4.1.1 +\subsubsection{GROESOLVE: Solution of a Set of Polynomial Equations} +\ttindex{GROESOLVE} \ttindex{GROEBNERF} +The GROESOLVE operator incorporates a macro algorithm; +lexical Gr\"obner bases are computed by GROEBNERF and decomposed +into simpler ones by ideal decomposition techniques; if algebraically +possible, the problem is reduced to univariate polynomials which are +solved by SOLVE; if ROUNDED is on, numerical approximations are +computed for the roots of the univariate polynomials. +\[ + GROESOLVE(\{exp1, exp2, \ldots , expm\}[,\{var1, var2, \ldots , +varn\}]); \] +where $\{exp1, exp2,\ldots , expm\}$ is a list of any number of +expressions or equations, $\{var1, var2, \ldots , varn\}$ is an +optional list of variables. + +The result is a set of subsets. The subsets contain the solutions of the +polynomial equations. If there are only finitely many solutions, +then each subset is a set of expressions of triangular type +$\{exp1, exp2,\ldots , expn\},$ where $exp1$ depends only on +$var1,$ $exp2$ depends only on $var1$ and $var2$ etc. until $expn$ which +depends on $var1,\ldots,varn.$ This allows a successive determination of +the solution components. If there are infinitely many solutions, +some subsets consist in less than $n$ expressions. By considering some +of the variables as ``free parameters'', these subsets are usually +again of triangular type. + + +\example (intersections of a line with a circle): +\index{GROEBNER package ! example} + +\[ +GROESOLVE(\{x**2 - y**2 - a, p*x+q*y+s\},\{x,y\}); +\] +%{\small +\begin{verbatim} + 2 2 2 2 2 + {{X=(SQRT( - A*P + A*Q + S )*Q - P*S)/(P - Q ), + 2 2 2 2 2 + Y= - (SQRT( - A*P + A*Q + S )*P - Q*S)/(P - Q )}, + 2 2 2 2 2 + {X= - (SQRT( - A*P + A*Q + S )*Q + P*S)/(P - Q ), + 2 2 2 2 2 + Y=(SQRT( - A*P + A*Q + S )*P + Q*S)/(P - Q )}} +\end{verbatim} +%} +% Subsection 4.1.2 +\subsubsection{GROEPOSTPROC: Postprocessing of a Gr\"obner Basis} +\ttindex{GROEPOSTPROC} +In many cases, it is difficult to do the general Gr\"obner processing. +If a Gr\"obner basis with a {\it lex} ordering is calculated already (e.g., +by very individual parameter settings), the solutions can be derived +from it by a call to GROEPOSTPROC. GROESOLVE is functionally +equivalent to a call to GROEBNERF and subsequent calls to +GROEPOSTPROC for each partial basis. +\[ + GROEPOSTPROC(\{exp1, exp2, \ldots , expm\}[,\{var1, var2, \ldots , +varn\}]); +\] +where $\{exp1, exp2, \ldots , expm\}$ is a list of any number of +expressions, \linebreak[4] $\{var1, var2, \ldots ,$ $ varn\}$ is an +optional list of variables. The expressions must be a {\it lex} Gr\"obner +basis with the given variables; the ordering must be still active. + +The result is the same as with GROESOLVE. + +\begin{verbatim} +groepostproc({x3**2 + x3 + x2 - 1, + x2*x3 + x1*x3 + x3 + x1*x2 + x1 + 2, + x2**2 + 2*x2 - 1, + x1**2 - 2},{x3,x2,x1}); + +{{X3= - SQRT(2), + + X2=SQRT(2) - 1, + + X1=SQRT(2)}, + + {X3=SQRT(2), + + X2= - (SQRT(2) + 1), + + X1= - SQRT(2)}, + + SQRT(4*SQRT(2) + 9) - 1 + {X3=-------------------------, + 2 + + X2= - (SQRT(2) + 1), + + X1=SQRT(2)}, + + - (SQRT(4*SQRT(2) + 9) + 1) + {X3=------------------------------, + 2 + + X2= - (SQRT(2) + 1), + + X1=SQRT(2)}, + + SQRT( - 4*SQRT(2) + 9) - 1 + {X3=----------------------------, + 2 + + X2=SQRT(2) - 1, + + X1= - SQRT(2)}, + + - (SQRT( - 4*SQRT(2) + 9) + 1) + {X3=---------------------------------, + 2 + + X2=SQRT(2) - 1, + + X1= - SQRT(2)}} +\end{verbatim} + +% Subsection 4.1.3 +\subsubsection{IDEALQUOTIENT: Quotient of an Ideal and an Expression} +\ttindex{IDEALQUOTIENT} \index{ideal quotient} +Let $I$ be an ideal and $f$ be a polynomial in the same +variables. Then the algebraic quotient is defined by +\[ +I:f = \{ p \;| \; p * f \;\mbox{ member of }\; I\}\;. +\] +The ideal quotient $I:f$ contains $I$ and is obviously part of the +whole polynomial ring, i.e. contained in $\{1\}$. The case $I:f = +\{1\}$ is equivalent to $f$ being a member of $I$. The other extremal +case, $I:f=I$, occurs, when $f$ does not vanish at any general zero of $I$. +The explanation of the notion ``general zero'' introduced by van der +Waerden, however, is beyond the aim of this manual. The operation +of GROESOLVE/GROEPOSTPROC is based on nested ideal quotient +calculations. + +If $I$ is given by a basis and $f$ is given as an expression, the +quotient can be calculated by +\[ +IDEALQUOTIENT (\{exp1, \ldots , expm\}, exp); \] +where $\{exp1, exp2, \ldots , expm\}$ is a list of any number of +expressions or equations, {\it exp} is a single expression or equation. + +IDEALQUOTIENT calculates the algebraic quotient of the ideal $I$ +with the basis $\{exp1, exp2, \ldots , expm\}$ and {\it exp} with +respect to the variables given or extracted. $\{exp1, exp2, \ldots , +expm\}$ is not necessarily a Gr\"obner basis. +The result is the Gr\"obner basis of +the quotient. + +\subsection{Operators for Gr\"obner Bases in all Term Orderings} +\index{Hilbert polynomial} +In some cases where no Gr\"obner +basis with lexical ordering can be calculated, a calculation with a total +degree ordering is still possible. Then the Hilbert polynomial gives +information about the dimension of the solutions space and for finite +sets of solutions univariate polynomials can be calculated. The solutions +of the equation system then is contained in the cross product of all +solutions of all univariate polynomials. + +\subsubsection{HILBERTPOLYNOMIAL: Hilbert Polynomial of an Ideal} +\ttindex{HILBERTPOLYNOMIAL} +This algorithm was contributed by {\sc Joachim Hollman}, Royal +Institute of Technology, Stockholm (private communication). + +\[ +HILBERTPOLYNOMIAL (\{exp1, \ldots , expm\})\;; +\] +where $\{exp1, exp2, \ldots , expm\}$ is a list of any number of +expressions or equations. + +HILBERTPOLYNOMIAL calculates the Hilbert polynomial of the ideal +with basis $\{exp1, exp2, \ldots , expm\}$ with respect to the +variables given or extracted provided the given term ordering is +compatible with the degree, such as the GRADLEX- or REVGRADLEX-ordering. +The term ordering of the basis +must be active and $\{exp1, exp2,\ldots$, $ expm\}$ should be a +Gr\"obner basis with respect to this ordering. The Hilbert polynomial +gives information about the cardinality of solutions of the system +$\{exp1, exp2, \ldots , expm\}$: if the Hilbert polynomial is an +integer, the system has only a discrete set of solutions and the +polynomial is identical with the number of solutions counted with +their multiplicities. Otherwise the degree of the Hilbert +polynomial is the dimension of the solution space. + +If the Hilbert polynomial is not a constant, it is constructed with the +variable ``X'' regardless of whether $x$ is member of $\{var1, var2, +\ldots , varn\}$ or not. The value of this polynomial at sufficiently +large numbers ``X'' +is the difference +of the dimension of the linear vector space of all polynomials of degree +$ \leq X $ minus the dimension of the subspace of all polynomials of +degree $\leq X $ which belong also to the ideal. + +\paragraph{Remark:} The number of zeros in an ideal and the +Hilbert polynomial depend only on the leading terms of the +Gr\"obner basis. So if a subsequent Hilbert calculation is planned, the +Gr\"obner calculation should be performed with ON GLTBASIS and +the value of GLTB (or its elements in a GROEBNERF context) should be +given to HILBERTPOLYNOMIAL. In this manner, a lot of computing time can be +saved in the case of large bases. + +% Chapter 5. +\section{Calculations ``by Hand''} +The following operators support explicit calculations with +polynomials in a distributive representation at the REDUCE top level. +So they allow one to do Gr\"obner type evaluations stepwise by +separate calls. Note that the normal REDUCE arithmetic can be used +for arithmetic combinations of monomials and polynomials. + +% Subsection 5.1 +\subsection{Representing Polynomials in Distributive Form} +\ttindex{GSORT} +\[ + GSORT (p); +\] +where $p$ is a polynomial or a list of polynomials. + +If $p$ is a single polynomial, the result is a reordered version of $p$ +in the distributive representation according to the variables and the +current term order mode; if $p$ is a list, its members are converted +into distributive representation and the result is the list sorted by +the term ordering of the leading terms; zero polynomials are +eliminated from the result. + +\begin{verbatim} + torder({alpha,beta,gamma},lex); + dip := gsort(gamma*(alpha-1)**2*(beta+1)**2); + + + 2 2 2 + DIP := ALPHA *BETA *GAMMA + 2*ALPHA *BETA*GAMMA + + 2 2 + + ALPHA *GAMMA - 2*ALPHA*BETA *GAMMA - 4*ALPHA*BETA*GAMMA + + 2 + - 2*ALPHA*GAMMA + BETA *GAMMA + 2*BETA*GAMMA + GAMMA + + \end{verbatim} + + +% Subsection 5.2 +\subsection{Splitting of a Polynomial into Leading Term and Reductum} +\ttindex{GSPLIT} +\[ +GSPLIT (p); +\] +where $p$ is a polynomial. + +GSPLIT converts the polynomial $p$ into distributive representation +and splits it into leading monomial and reductum. The result is a list +with two elements, the leading monomial and the reductum. + +\begin{verbatim} + gslit(dip); + + 2 2 + {ALPHA *BETA *GAMMA, + + 2 2 2 + 2*ALPHA *BETA*GAMMA + ALPHA *GAMMA - 2*ALPHA*BETA *GAMMA + + 2 + - 4*ALPHA*BETA*GAMMA - 2*ALPHA*GAMMA + BETA *GAMMA + + + + 2*BETA*GAMMA + GAMMA} + + \end{verbatim} + + +\subsection{Calculation of Buchberger's S-polynomial} +\ttindex{GSPOLY} +\[ +GSPOLY (p1,p2); +\] +where $p1$ and $p2$ are polynomials. + +GSPOLY calculates the $S$-polynomial from $p1$ and $p2$; + +Example for a complete calculation (taken from {\sc Davenport et al.} + \cite{Davenport:88a}): +\begin{verbatim} + torder({x,y,z},lex)$ + g1 := x**3*y*z - x*z**2; + g2 := x*y**2*z - x*y*z; + g3 := x**2*y**2 - z;$ + + % first S-polynomial + + g4 := gspoly(g2,g3);$ + + 2 2 + G4 := X *Y*Z - Z + + % next S-polynomial + + p := gspoly(g2,g4); $ + + 2 2 + P := X *Y*Z - Y*Z + + % and reducing, here only by g4 + + g5 := preduce(p,{g4}); + + 2 2 + G5 := - Y*Z + Z + + % last S-polynomial} + + g6 := gspoly(g4,g5); + + 2 2 3 + G6 := X *Z - Z + + % and the final basis sorted descending + + gsort{g2,g3,g4,g5,g6}; + + 2 2 + {X *Y - Z, + + 2 2 + X *Y*Z - Z , + + 2 2 3 + X *Z - Z , + + 2 + X*Y *Z - X*Y*Z, + + 2 2 + - Y*Z + Z } + \end{verbatim} + +\bibliography{groebner} +\bibliographystyle{plain} +\end{document} +