\hoffset -.5cm
%\voffset 1cm
\documentstyle {article}
\setlength{\parindent}{.5cm}
\setlength{\parskip}{2mm}
\addtolength{\textheight}{1cm}
\newcommand{\mexp}{\mbox{exp}}
\newcommand{\lstar}{\mbox {\large $*$}}
\newcommand{\ldag}{\mbox {\large $\dagger$}}
\newtheorem{Theorem}{Theorem}
\begin{document}
\pagestyle{plain}
\vspace*{1cm}
\begin{center}
{\LARGE {\bf GROEBNER}} \vspace*{.5cm}\par
{\LARGE {A Package for Calculating Groebner Bases}}
\vspace*{.5cm}\par
{\large H. Melenk}$\,^{\lstar}$ \hspace*{1cm} {\large H.M. M\"oller}$
\,^{\ldag}$\hspace*{1cm} {\large W. Neun}$\,^{\lstar}$
\end{center}
\begin{center}
\begin{tabular}{ll}
{$\lstar$} & {\large Konrad--Zuse--Zentrum} \\
& {\large f\"ur Informationstechnik Berlin} \\
& {\large Heilbronner Strasse 10} \\
& {\large D--1000 Berlin 31} \\
& {\large Federal Republic of Germany} \\
& {\large E--mail: Melenk@sc.zib--berlin.de} \\ \\
{$\ldag$} & {\large Fernuniversit\"at Hagen} \\
& {\large FB Math und Informatik} \\
& {\large Postfach 940} \\
& {\large D--5800 Hagen} \\
& {\large Federal Republic of Germany}\\
& {\large E--mail: MA105@DHAFEU11.bitnet}
\end{tabular}
\end{center}
\vspace*{.5cm}\par
Groebner 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 Groebner bases, a survey of possible applications and further
references, see \cite{BUCH85}. Examples are given in \cite{BOGEK86},
in \cite{BUCH88} and also in the test file for this package.
The GROEBNER package calculates Groebner 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 {\sc R. Gebauer, A.C. Hearn, H. Kredel, M.
M\"oller}. The algorithms implemented in the current version are
documented in \cite{FGLM} and \cite{GEMO88}.
\newpage
\subsubsection*{Incompatibilities with the Groebner package in
REDUCE 3.3:}
\begin{itemize}
\item In contrast to the previous version, the polynomials in the
Groebner bases by default now have non fractional coefficients;
the fractional forms can be generated by dividing each polynomial
by its leading coefficient or by setting ON RATIONAL.
\item The routines GREDUCE and PREDUCE now avoid fractional coefficients
by reducing a constant multiple of the input polynomial instead of the
polynomial itself (``pseudo reduction'' ) as long as RATIONAL is off.
\item The term order modes were cleaned up so that their names
now correspond to the literature:
\begin{center}
\begin{tabular}{c}
INVLEX $\rightarrow$ LEX, INVTOTALDEGREE $\rightarrow$
GRADLEX, \\
TOTALDEGREE $\rightarrow$ REVGRADLEX
\end{tabular}
\end{center}
For compatibility reasons, the old names (except the old LEX, which
did not represent an order usable in the Groebner context) are
still supported.
\end{itemize}
\newpage
\tableofcontents
\newpage
% Chapter 1
\pagestyle{plain}
\section{Background}
% Section 1.1
\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 (optional parameter) 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, which 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 the faster one
(compared in cases where both are applicable). 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.
%Section 1.2
\subsection{Term Ordering} \par
In the theory of Groebner bases, the terms of polynomials are
considered as ordered. The following order modes are available in
the current package:
\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.
\subsubsection*{Examples with $\{x,y,z\}$:}
\[
\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**3 * y**3 & \gg & y**3 * z**3 & \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**3 * y**3 & \ll & y**3 * z**3 & \mbox{(equal total degree,} \\
& & & \mbox{so reverse order of LEX)}
\end{array}
\]
The formal description of the term order modes is similar to
\cite{KRED88}; 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) <lex<
(0)
\end{array}
\]
Note that the LEX ordering is identical to the standard REDUCE
kernel ordering, when KORDER is set explicitly to the sequence of
variables.
LEX is the default term order mode in the Groebner package.
It is beyond the scope of this manual to discuss the functionality of
the term order modes. See \cite{BUCH88}.
Most operators in this package accept a list of variables as an
optional last parameter. If this parameter is given explicitly, it
defines the names of the variables and their sequence at the same
time. If the parameter is omitted, the variables are extracted from
the expressions automatically and the REDUCE system order defines
their sequence; this can be influenced by setting an explicit order
via the KORDER statement.
The result of a Groebner calculation is algebraically correct only
with respect to the term order mode and the variable sequence
which was in effect during the calculation. This is important if
several calls to the Groebner package are done with the result of the
first being the input of the second call.
% Section 1.3
\subsection{The Buchberger Algorithm}
The Buchberger algorithm of the package is based on {\sc
Gebauer/M\"oller} \cite{GEMO88}. Most of the
improvements are documented in \cite{MEMON88}.
% Chapter 2
\section{Loading of the Package}
The following command loads the Groebner basis package into
REDUCE (this syntax may vary according to implementation):
\begin{center}
load groebner;
\end{center}
The package contains various operators, and switches for control
over the reduction process. These are discussed in the following.
% Chapter 3
\section{The Basic Operators}
% Section 3.1
\subsection{Term Ordering Mode}
\begin{description}
\item [{\it TORDER}] $m$;
where $m$ is the name of a term ordering mode LEX, GRADLEX,
REV\-GRAD\-LEX (or another implemented mode).
TORDER sets the term ordering mode. The default mode is LEX. The
previous ordering mode is returned.
\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 Groebner
calculation. \end{description}
% Section 3.2
\subsection{GROEBNER: Calculation of a Groebner Basis}
\begin{description}
\item[{\it GROEBNER}] $(\{exp1, exp2, \ldots , expm\}[,\{var1, var2,
\ldots , varn\}]); $
where $\{exp1, exp2, \ldots , expm\}$is a list of
expressions or equations, and \linebreak[4] $\{var1, var2, \ldots ,
varn\}$ is an optional list of variables.
GROEBNER calculates the Groebner basis of the given set of
expressions with respect to the given set of variables in the order
given. If the variable list is omitted, the variables in the expression
list are used, ordered according to the system variable order. The
Groebner basis is a list of polynomials.
The Groebner 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
\begin{center}
gvarslast .
\end{center}
This is important if the variables are extracted automatically or if
the variables are reordered because of optimization and if the
sequences are needed afterwards for subsequent calculations (e.g.
for GREDUCE).
\end{description}
\subsubsection*{Examples:}
${\it groebner} (\{ 3*x**2*y + 2*x*y + y + 9*x**2 + 5*x - 3, $ \\
\hspace*{+1cm}$2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x + 3,$ \\
\hspace*{+1cm}$x**3*y + x**2*y + 3*x**3 + 2*x**2 \}); $
%{\small
\begin{verbatim}
2
{8*X - 2*Y + 5*Y + 3,
3 2
2*Y - 3*Y - 16*Y + 21}
\end{verbatim}
%}
{\it gvarslast}; \\
%{\small
\begin{verbatim}
{X,Y}
\end{verbatim}
%}
This example used the default system variable ordering, which was
$\{x,y\}$. With the other variable ordering, a different basis results:
{\it groebner} $(\{ 3*x**2*y + 2*x*y + y + 9*x**2 + 5*x = 3,$ \\
\hspace*{+1cm} $2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x = -3,$ \\
\hspace*{+1cm} $x**3*y + x**2*y + 3*x**3 + 2*x**2 \}, \{y,x\})$;
%{\small
\begin{verbatim}
2
{2*Y + 2*X - 3*X - 6,
3 2
2*X - 5*X - 5*X}
\end{verbatim}
%}
Another basis yet again results with a different term ordering:
\begin{center}
{\it torder revgradlex;}
\end{center}
LEX
{\it groebner} $(\{ 3*x**2*y + 2*x*y + y + 9*x**2 + 5*x = 3,$ \\
\hspace*{+1cm} $2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x = -3,$ \\
\hspace*{+1cm} $x**3*y + x**2*y + 3*x**3 + 2*x**2 \}, \{y,x\}); $
%{\small
\begin{verbatim}
2
{2*X - 3*X + 2*Y - 6,
X*Y + X - Y + 3,
2
2*Y - 8*X - 5*Y - 3}
\end{verbatim}
%}
The operation of GROEBNER can be controlled by the following
switches:
\begin{description}
\item[GROEBOPT] -- If set ON, the sequence of variables is optimized
with respect to execution speed; the algorithm involved is described
in \cite{BOGEK86}; note that the final list of variables is available in
GVARSLAST.
An explicitly declared dependency supersedes the
variable optimization. For example
\begin{center}
{\it depend} $a$, $x$, $y$;
\end{center}
guarantees that $a$ will be placed in front of $x$ and $y$. So
GROEBOPT can be used even in cases where elimination of variables is
desired.
By default GROEBOPT is off, conserving the original variable
sequence.
\item[GROEBPREREDUCE] -- If set ON, GROEBNER tries to simplify the
input expressions: if the head term of an input expression is a
multiple of the head term of another expression, it can be reduced;
these reductions are done cyclicly as long as possible in order to
shorten the main part of the algorithm.
By default GROEBPREREDUCE is off;
\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.
\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}
The following switches control the print output of GROEBNER; by
default all these switches are set OFF and nothing is printed.
\begin{description}
\item[GROEBSTAT] -- A summary of the computation is printed
including the computing time, the number of intermediate
$H$--polynomials and the counters for the hits of the criteria.
\item[TRGROEB] -- Includes GROEBSTAT and the printing of the
intermediate $H$-polynomials.
\item[TRGROEBS] -- Includes TRGROEB and the printing of
intermediate $S$--poly\-nomials.
\item[TRGROEB1] -- The internal pairlist is printed when modified.
\end{description}
%Section3.3new
\subsection{GZERODIM?: Test of $\dim = 0$}
\begin{description}
\item[{\it GZERODIM}!?] $\left(bas[,\{var1,\ldots , varn\}]\right)$ \\
where {\it bas} is a Groebner basis in the current ordering with the
specified variables. 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, 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}
%Section 3.4new
\subsection{GLEXCONVERT: Conversion of an Arbitrary Groebner Basis
into a Lexical One}
\begin{description}
\item[{\it GLEXCONVERT}] $ \left(\{exp,\ldots , expm\} \left[,\{var1
\ldots , varn\}\right]\left[,MAXDEG=mx\right]\right.$ \\
$\left.\left[,NEWVARS=\{nv1, \ldots , nvk\}\right]\right) $ \\
when $\{exp1, \ldots , expm\}$ is Groebner basis with variables
$\{var1, \ldots , varn\}$ in the current term order mode,
$mx$ is an integer,
$\{nv1, \ldots , nvk\}$ is a subset of the basis variables.
\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 by
\linebreak[4] {\sc Faug{\`e}re}, {\sc Gianni}, {\sc Lazard} and {\sc
Mora} \cite{FGLM}. In general, the calculation of a Groebner 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 polynomial exists.
\subsubsection*{Example:}
{\it torder gradlex;}
$ g := groebner (\{ f1 := 45*p + 35*s -165*b -36,$ \\
\hspace*{+1cm} $35*p + 40*z + 25*t - 27*s, 15*w + 25*p*s +30*z -18*t $ \\
\hspace*{+1cm} $-165*b**2, -9*w + 15*p*t + 20*z*s, $ \\
\hspace*{+1cm} $ w*p + 2*z*t - 11*b**3, 99*w - 11*s*b +3*b**2, $ \\
\hspace*{+1cm} $ b**2 + 33/50*b + 2673/10000\}, \{w,p,z,t,s,b\});$
\begin{verbatim}
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}
\end{verbatim}
{\it
glexconvert}$\left(g,\{w,p,z,t,s,b\},maxdeg=5,newvars=\{w\}\right)$
\begin{verbatim}
2
100000000*W + 2780000*W + 416421
\end{verbatim}
{\it glexconvert}$\left(g,\{w,p,z,t,s,b\},maxdeg=5,
newvars=\{p\}\right),$
\begin{verbatim}
2
6000*P - 2360*P + 3051
\end{verbatim}
% Section 3.4
\subsection{GROEBNERF: Factorizing Groebner Bases}
% Subsection 3.4.1
\subsubsection{Background}
If Groebner 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, e.g. $h= f*g$,
then $h$ vanishes if and only if one of the factors vanishes. So if
during the calculation of a Groebner 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) Groebner 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, i.e. no additional solution for the original problem,
contributed by this branch.
% Subsection 3.4.2
\subsubsection{GROEBNERF Call}
The syntax of GROEBNERF is the same as for GROEBNER.
\[
\mbox{\it GROEBNERF}(\{exp1, exp2, \ldots , expm\}[,\{var1, var2,
\ldots , varn\}]);
\]
where $\{exp1, exp2, \ldots , expm\} $ is a list of expressions or
equations, \linebreak[4] and $\{var1, var2,\ldots , varn\}$ is an
optional list of variables.
GROEBNERF tries to separate polynomials into individual factors and
to branch the computation in a recursive manner (factorization tree).
The result is a list of partial Groebner bases. If no factorization 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 factorizing is controlled by some switches.
As a side effect, the sequence of variables is stored as 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.
\subsubsection*{Example:}
{\it groebnerf} $(\{ 3*x**2*y + 2*x*y + y + 9*x**2 + 5*x = 3,$ \\
\hspace*{+1cm} $ 2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x = -3, $\\
\hspace*{+1cm} $ x**3*y + x**2*y + 3*x**3 + 2*x**2 \}, \{y,x\});$
%{\small
\begin{verbatim}
{{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:
\begin{center}
\begin{tabular}{l}
GROEBOPT \\
GROEBPREREDUCE \\
GLTBASIS \\
GROEBFULLREDUCTION \\
GROEBSTAT \\
TRGROEB \\
TRGROEBS \\
TRGROEB1
\end{tabular}
\end{center}
\subsubsection*{Additional switches for GROEBNERF:}
\begin{description}
\item[GROEBRES] -- If ON, a resultant is calculated under certain
circumstances (one bivariate $H$--polynomial is followed by another
one). This shortens the calculation sometimes.
By default GROEBRES is off.
\item[TRGROEBR] -- All intermediate partial basis are printed when
detected.
By default TRGROEBR is off.
\end{description}
{\bf GROEBMONFAC GROEBRESMAX GROEBRESTRICTION} \\
\hspace*{.5cm} These variables are described in the following
paragraphs.
% Subsection 3.4.3
\subsubsection{Suppression of Monomial Factors}
The factorization in GROEBNERF is controlled by the following
switches and variables. The variable GROEBMONFAC is connected to
the handling of ``monomial factors". A monomial factor is a product
of variable powers as a factor, e.g. $ x**2*y$ in $x**3*y -
2*x**2*y**2$. A monomial factor represents a solution of the type
``$ x = 0$ or $y = 0$" with a certain multiplicity. With
GROEB\-NERF
the multiplicity of monomial factors is lowered to the value of the
shared variable
\begin{center}
GROEBMONFAC
\end{center}
which by default is 1 (= monomial factors remain present, but their
multiplicity is brought down). With
\begin{center}
GROEBMONFAC := 0
\end{center}
the monomial factors are suppressed completely.
\subsubsection*{Example:}
(Equations extracted from a differential equation system for a
chemical reaction system for pyridine, in: {\sc
Ebert/Deuflhard/Jaeger} (1981) \cite{EDJ81}). \[
\begin{array}{lll}
f1 & := & -1*A + p9*B; \\
f2 & := & p1*A - p2*B - p3*C*B + p7*D - p9*B + p10*D*F; \\
f3 & := & p2*B - p3*B*C - 2*p4*C*C - p6*C + p8*E \\
& & \;\;+ p10*D*F + 2*p11*E*F;\\
f4 & := & p3*B*C - p5*D - p7*D - p10*D*F; \\
f5 & := & p4*C*C + p5*D -p8*E - p11*E*F; \\
f6 & := & p3*B*C + p4*C*C + p6*C - p10*D*F - p11*E*F; \\
f7 & := & p6*C + p7*D + p8*E; \\
\multicolumn{3}{l}{\mbox{\it polys}\; :=\;\{f1,f2,f3,f4,f5,f6,f7\} \$ \,vars\; :
=\;
\{A,B,C,D,E,F\}\$} \\
\multicolumn{3}{l}{\mbox{\it groebmonfac}\; :=\; 1; \%\mbox{\it
allowing monomial factors with exponent $1$}} \\
\multicolumn{3}{l}{\mbox{\it res} \;:=\; \mbox{\it groebnerf
$($polys,vars$)$};}
\end{array}
\]
%{\small
\begin{verbatim}
RES := {{A,E,B,D,C},
{A, - E*P8 - C*P6,B,F*P6*P11 + C*P4*P8 + P6*P8,D}}
% the above result has two partial bases; they have in common that
% A,B and D are forced to zero
\end{verbatim}
%}
groebmonfac := 0; \% now suppressing monomial factors at all
\[
\mbox{\it res} := \mbox{\it groebnerf }(\mbox{\it polys,vars});
\]
%{\small
\begin{verbatim}
RES := {{1}};
% with this configuration there is no solution at all. (The
% system has no solution with only nonzero variable values)
\end{verbatim}
%}
% Subsection 3.4.4
\subsubsection{Limitation on the Number of Results}
The shared variable
\begin{center}
GROEBRESMAX
\end{center}
controls the number of partial results. Its default value is 300. If
groebresmax partial results are calculated, the calculation is
terminated.
% Subsection 3.4.5
\subsubsection{Restriction to Real Nonnegative Solutions}
In some applications only nonnegative values or positive definite
values for the variables are interesting as solutions for a given set
of equations. 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. By setting the shared variable
\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.
\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.
% Section 3.6
\subsection{GREDUCE, PREDUCE: Reduction of Polynomials}
% Subsection 3.6.1
\subsubsection{Background}
Reduction of a polynomial ``p" modulo a given sets of polynomials
``B" is done by the reduction algorithm incorporated in the
Buchberger algorithm. Informally it can be described for
polynomials over a field as follows:
\begin{center}
\begin{tabular}{l}
loop1: \hspace*{2mm}\% head term elimination \\
\hspace*{-1cm} if there is one polynomial $b$ in $B$ such that the
leading \\ term of $p$ is a multiple of the leading term of $p$ do \\
$p := p - lt(p)/lt(b) * b$ (the leading term vanishes)\\
\hspace*{-1cm} do this loop as long as possible; \\
loop2: \hspace*{2mm} \% elimination of subsequent terms \\
\hspace*{-1cm} for each term $s$ in $p$ do \\
if there is one polynomial $b$ in $B$ such that $s$ is a\\
multiple of the leading term of $p$ do \\
$p := p - s/lt(b) * b$ (the term $s$ vanishes) \\
\hspace*{-1cm}do this loop as long as possible;
\end{tabular}
\end{center}
If the coefficients are taken from a ring without zero divisors we
cannot divide by each possible number like in the field case. But
using that in the field case $c*p $ is reduced to $c*q $, if $ p $
is reduced to $ q $, for arbitrary numbers $ c $, the reduction for
the ring case uses the least $ c $ which makes the (field) reduction
for $ c*p $ integer. The result of this reduction is returned as
(ring) reduction of $ p $ eventually after removing the content, i.e.
the greatest common divisor of the coefficients. The result of this
type of reduction is also called a pseudo reduction of $ p $.
% Subsection 3.5.2
\subsubsection{Reduction via Groebner Basis Calculation}
\[
\mbox{\it GREDUCE}(exp, \{exp1, exp2, \ldots , expm\}[,\{var1, var2,
\ldots , varn\}]);
\]
where {\it exp} is an expression, and $\{exp1, exp2,\ldots , expm\}$ is
a list of any number of expressions or equations and $\{var1, var2,$
$\ldots , varn\}$ is an optional list of variables.
GREDUCE first converts the list of expressions $\{exp1, \ldots ,
expn\}$ to a Groeb\-ner 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*{Example:}
(Note: This example assumes a new session, and not the above
settings.)
{\it greduce} $( 5*y**2 + 2*x**2*y + 5/2*x*y + 3/2*y$\\
\hspace*{+1cm} $ + 8*x**2 + 3/2*x - 9/2, $\\
\hspace*{+1cm} $\{ 3*x**2*y + 2*x*y + y + 9*x**2 + 5*x - 3,$ \\
\hspace*{+1cm} $ 2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x + 3,$ \\
\hspace*{+1cm} $ x**3*y + x**2*y + 3*x**3 + 2*x**2 \});$
%{\small
\begin{verbatim}
2
Y
\end{verbatim}
%}
% Subsection 3.5.3
\subsubsection{Reduction with Respect to Arbitrary Polynomials}
\[
PREDUCE(exp, \{exp1, exp2,\ldots , expm\}[,\{var1, var2,\ldots ,
varn\}]);
\]
where $ exp $ is an expression, and $\{exp1, exp2, \ldots ,
expm \}$ is a list of any number of expressions or equations and
$\{var1, var2, \ldots , varn\}$ is an optional list of variables.
PREDUCE reduces the given expression modulo the set $\{exp1,
\ldots , expm\}$. If this set is a Groebner basis, the obtained reduced
expression is uniquely determined. If not, then it depends on the
subsequence of the single reduction steps (see 3.6.1). PREDUCE does
not check, whether $\{exp1, exp2, \ldots , expm\}$ is a Groebner
basis in the actual order. Therefore, if the expressions are a
Groebner basis calculated earlier with a variable sequence given
explicitly or modified by optimization, the sequence of variables
should be given as a parameter explicitly.
\subsubsection*{Example (PREDUCE with an arbitrary set of
polynomials):}
{\it preduce} $ ( 5*y**2 + 2*x**2*y + 5/2*x*y + 3/2*y + 8*x**2 +
3/2*x - 9/2, $ \\ \hspace*{+1cm} $ \{ 3*x**2*y + 2*x*y + y + 9*x**2 +
5*x - 3, $ \\ \hspace*{+1cm} $ 2*x**3*y - x*y - y + 6*x**3 - 2*x**2 -
3*x + 3, $ \\ \hspace*{+1cm} $ x**3*y + x**2*y + 3*x**3 + 2*x**2 \});
$
%{\small
\begin{verbatim}
2 2
12*X + 7*X*Y - 11*X + 30*Y + 5*Y - 15
\end{verbatim}
%}
\subsubsection*{Example (PREDUCE called with a Groebner basis):}
\[
\begin{array}{ll}
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 \}) \\
\multicolumn{2}{l}{preduce (5*y**2 + 2*x**2*y + 5/2*x*y + 3/2*y} \\
\multicolumn{2}{l}{\hspace*{+1cm}+ 8*x**2 + 3/2*x - 9/2, gb);}
\end{array}
\]
%{\small
\begin{verbatim}
2
Y
\end{verbatim}
%}
% Subsection 3.5.4
\subsubsection{Reduction Tree}
In some case not only the results produced by GREDUCE and
PREDUCE are of interest, but the reduction process is of some value
too. If the switch
\begin{center}
GROEBPROT
\end{center}
is set on, GREDUCE and PREDUCE produce as a side effect a trace of
their work as a REDUCE list of equations in the shared variable
\begin{center}
GROEBPROTFILE.
\end{center}
Its value is a list of equations with a variable ``candidate" playing
the role of the object to be reduced. The polynomials are cited as
$``poly1", ``poly2", \ldots\;.$ If read as assignments, these equations
form a program which leads from the reduction input to its result.
Note that, due to the pseudo reduction with a ring as the coefficient
domain, the input coefficients may be changed by global factors.
\subsubsection*{ Example:}
{\it on groebprot} \$ \\
{\it preduce} $ (5*y**2 + 2*x**2*y + 5/2*x*y + 3/2*y + 8*x**2 $ \\
\hspace*{+1cm} $+ 3/2*x - 9/2, gb);$
\begin{verbatim}
2
Y
\end{verbatim}
{\it groebprotfile;}
\begin{verbatim}
2 2 2
{CANDIDATE=4*X *Y + 16*X + 5*X*Y + 3*X + 10*Y + 3*Y - 9,
2
POLY1=8*X - 2*Y + 5*Y + 3,
3 2
POLY2=2*Y - 3*Y - 16*Y + 21,
CANDIDATE=2*CANDIDATE,
CANDIDATE= - X*Y*POLY1 + CANDIDATE,
CANDIDATE= - 4*X*POLY1 + CANDIDATE,
CANDIDATE=4*CANDIDATE,
3
CANDIDATE= - Y *POLY1 + CANDIDATE,
CANDIDATE=2*CANDIDATE,
2
CANDIDATE= - 3*Y *POLY1 + CANDIDATE,
CANDIDATE=13*Y*POLY1 + CANDIDATE,
CANDIDATE=CANDIDATE + 6*POLY1,
2
CANDIDATE= - 2*Y *POLY2 + CANDIDATE,
CANDIDATE= - Y*POLY2 + CANDIDATE,
CANDIDATE=CANDIDATE + 6*POLY2}
\end{verbatim}
This means
\begin{eqnarray*}
\lefteqn{
16 (5 y^2 + 2 x^2 y + \frac{5}{2} x y + \frac{3}{2} y + 8 x^2+ \frac{3}{2} x -
\frac{9}{2})=} \\ & &
(-8 x y -32 x -2 y^3 -3 y^2 + 13 y + 6) \mbox{POLY1} \\
& & \; + (-2 y^2 -2 y + 6) \mbox{POLY2 } \; + y^2.
\end{eqnarray*}
% new 3.6/Sept 21
\subsection{Tracing with GROEBNERT and PREDUCET}
Given a set of polynomials $\{f_1,\ldots ,f_k\}$ and their Groebner
basis $\{g_1,\ldots ,g_l\}$, it is well known that there are matrices of
polynomials $C_{ij}$ and $D_{ji}$ such that
\[
f_i = \displaystyle{\sum\limits_j} C_{ij} g_j \;\mbox{ and } g_j =
\displaystyle{\sum\limits_i} D_{ji} f_i
\]
and these relations are needed explicitly sometimes.
In {\sc Buchberger} \cite{BUCH85}, such cases are described in the
context of linear polynomial equations. The standard technique for
computing the above formulae is to perform
Groebner reductions, keeping track of the
computation in terms of the input data. In the current package such
calculations are performed with (an internally hidden) cofactor
technique: the user has to assign unique names to the input
expressions and the arithmetic combinations are done with the
expressions and with their names simultaneously. So the result is
accompanied by an expression which relates it algebraically to the
input values.
There are two complementary operators with this feature: GROEBNERT
and PREDUCET; functionally they correspond to GROEBNER and PREDUCE.
However, the sets of expressions here {\it {\bf must be}} equations
with unique single identifiers on their left side and the {\it lhs} are
interpreted as names of the expressions. Their results are
sets of equations (GROEBNERT) or equations (PREDUCET), where
a {\it lhs} is the computed value, while the {\it rhs} is its equivalent
in terms of the input names.
\paragraph{Example 1.}
We calculate the Groebner basis for an ellipse (named ``$p1$'' ) and a
line (named ``$p2$'' ); $p2$ is member of the basis immediately and so
the corresponding first result element is of a very simple form; the
second member is a combination of $p1$ and $p2$ as shown on the
{\it rhs} of this equation:
\noindent{\it
gb1:=groebnert$({p1=2*x**2+4*y**2-100,p2=2*x-y+1})$;}
\begin{verbatim} GB1 := {2*X - Y + 1=P2,
2
9*Y - 2*Y - 199= - 2*X*P2 - Y*P2 + 2*P1 + P2}
\end{verbatim}
\paragraph{Example 2.}
We want to reduce the polynomial \verb+ x**2+ {\it wrt}
the above Groebner basis and need knowledge about the reduction
formula. We therefore extract the basis polynomials from $GB1$,
assign unique names to them (here $G1$, $G2$) and call PREDUCET.
The polynomial to be reduced here is introduced with the name $Q$,
which then appears on the {\it rhs} of the result. If the name for the
polynomial is omitted, its formal value is used on the right side too.
\noindent{\it gb$2$ := for $k := 1:$length gb$1$ collect
$\Bigl(mkid(g,k) = lhs$ part$(gb1,k)\Bigr)$;}
\begin{verbatim}
2
GB2 := {G1=2*X - Y + 1,G2=9*Y - 2*Y - 199}
\end{verbatim}
\noindent{\it preducet$(q=x**2,gb2)$;}
\begin{verbatim}
- 16*Y + 208= - 18*X*G1 - 9*Y*G1 + 36*Q + 9*G1 - G2
\end{verbatim}
\noindent{\it preducet$(x**2,gb2)$;}
\begin{verbatim}
2
- 16*Y + 208=36*X - 18*X*G1 - 9*Y*G1 + 9*G1 - G2
\end{verbatim}
In both cases the output means
\[
x^2 = (\frac{1}{2} x + \frac{1}{4} y - \frac{1}{4}) G1
+ \frac{1}{36} G2 + (-\frac{4}{9} y + \frac{52}{9}).
\]
\paragraph{Example 3.}
If we reduce a polynomial which is member of the ideal, we
consequently get a result with {\it lhs} zero:
\noindent{\it preducet$(q=2*x**2+4*y**2-100,gb2)$; }
\begin{verbatim}
0= - 2*X*G1 - Y*G1 + 2*Q + G1 - G2
\end{verbatim}
This means
\[ Q = ( x + \frac{1}{2} y - \frac{1}{2}) G1 + \frac{1}{2} G2.
\]
With these operators the matrices $C_{ij}$ and $D_{ji}$ are available
implicitly, $D_{ji}$ as side effect of GROEBNERT, $C_{ij}$ by {\it calls}
of PREDUCET of $f_i$ {\it wrt} $\{g_j\}$. The latter by definition will
have the {\it lhs} zero and a {\it rhs} with linear $f_i$.
If $\{1\}$ is the Groebner basis, the GROEBNERT calculation gives
a ``proof", showing, how $1$ can be computed as combination of the
input polynomials.
\paragraph{Remark:} Compared to the non-tracing algorithms, these
operators are much more time consuming. So they are applicable
only on small sized problems.
% *** SO BESSER ??
%Section 3.8
\subsection{GROEBNERM: Groebner Bases for Modules}
Polynomial r-tuples
$(p1,\ldots,pr) $ can be added componentwise
and multiplied by $ p*(p1,\ldots,pr) := (p*p1,\ldots,p*pr) $
for arbitrary polynomials $p.$ Given finitely many of
such polynomial r-tuples $P1:=(p11,\ldots,p1r),\ldots,Pm:=(pm1,\ldots,pmr),$
the polynomial module
\[ M := \{ g1*P1 + \cdots + gm*Pm \mid g1,\ldots,gm \mbox{ polynomials} \}
\]
possesses a Groebner basis for arbitrary admissible term orderings and
arbitrary weights.
The operator GROEBNERM calculates the Groebner basis of the module
\[
\mbox{GROEBNERM } \bigl(\{expr1, \ldots , exprm\} [,\{var1, \ldots ,
varn\} [, \{w_1, \ldots , w_r] ] \bigr)
\]
where
\begin{quote}
$\{expr1, \ldots , exprm\}$ are r-tuples of polynomials written as list,
\linebreak[4]$\{var1, \ldots , varn\}$ is an optional list of variables and
$\{w_1, \ldots , w_r\}$ is a list of positive integers $<1000$.
\end{quote}
Alternatively the {\it expr} can be expression of the form
\[
p= \{pol1, \ldots , polr\}
\]
with a ``name"--variable as with GROEBNERT. In this case, a tracing
Groebner basis calculation is performed. The $\{w1, \ldots , wr\}$ are
weights assigned to the components of the vector space, if a graduated
ordering is active. If omitted, all components are weighted with 1.
\paragraph{Example:}
\[
\begin{array}{lll}
B & := & \{\{ 1 , 0 , 0 , 0 , 0 \}, \\
& & \;\;\{ 0 , 0 , 0 , 0 , -1\}, \\
& & \;\;\{ 0 , 0 , 0 , 1 , 0\}, \\
& & \;\;\{ 0 , 0 , -1 , 0 , x^2\}\}\$ \vspace*{4mm} \\
D & := & \{\{ -x , y , 1 , 0 , 0 \}, \\
& &\;\;\{ 0 ,5x^2 , y , 1 , 0 \}, \\
& &\;\;\{ 0 , 0 ,4x^2 , 5y , y\}, \\
& &\;\;\{ 0 , 5 , 0 , x^2 , y \}\};
\end{array}
\]
groebnerM (append$(b,d)\, ,\;\{x,y\}\,, \;\{4,4,5,6,7\}$);
\begin{verbatim}
2
{{0,5,0,X ,Y},
2
{0,0,-1,0,X },
{ - X,Y,1,0,0},
{1,0,0,0,0},
{0,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,0},
{0,0,0,0,-1}}
\end{verbatim}
\[
\begin{array}{lllll}
\mbox{Btagged} & := & \{t1 & = & \{ 1 , 0 , 0 , 0 , 0 \}, \\
& & \;\; t2 & = & \{ 0 , 0 , 0 , 0 , -1 \}, \\
& & \;\; t3 & = & \{ 0 , 0 , 0 , 1 , 0 \}, \\
& & \;\; t4 & = & \{ 0 , 0 , -1 , 0 , x^2 \}\}\$
\end{array}
\]
\noindent groebnerM (append(btagged,d) , $\{x,y\} \,, \;\{4,4,5,6,7\}$);
\begin{verbatim}
2
{{0,5,0,X ,Y},
2
{0,0,-1,0,X }=T4,
{ - X,Y,1,0,0},
{1,0,0,0,0}=T1,
2
- X *T3 + Y*T2
{0,1,0,0,0}=-----------------,
5
2
{0,0,1,0,0}= - X *T2 - T4,
{0,0,0,1,0}=T3,
{0,0,0,0,-1}=T2}
\end{verbatim}
%Section 3.9
\subsection{Additional Orderings}
Besides the basic orderings, there are ordering options which are used for
special purposes.
%Section 3.7.1
\subsubsection{Separating the Variables into Groups }
It is often desirable to separate variables
and formal parameters in a system of polynomials.
This can be done with a {\it lex} Groebner
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 Groebner basis will
eliminate the members of the first set, if algebraically possible. {\it
Torder} here gets an additional parameter which describe the
grouping
\begin{center}{\it
\begin{tabular}{l}
TORDER gradlexgradlex, n; \\
TORDER gradlexrevgradlex, n; \\
TORDER lexgradlex, n; \\
TORDER 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}
The statement
\begin{center}
\begin{tabular}{cl}
{\it TORDER} & weighted, $n_1,n_2,n_3 \ldots$ ; \\
or \\
{\it TORDER} & weighted, $\{n_1,n_2,\ldots\}$
\end{tabular}
\end{center}
establishes a graduated ordering, where the exponents first are
multiplied by the given weights. If there are less weight values than
variables, the weight 1 is added automatically.
\subsubsection{Arbitrary Ordering}
If none of the given orderings fulfills the requirements, the user can
supply a private ordering in form of a procedure:
\begin{center}
{\it TORDER} private, $\langle${\it name}$\rangle$;
\end{center}
where $\langle${\it name}$\rangle$ is the name of a procedure. This
procedure must have the following properties:
\begin{itemize}
\item written in symbolic mode (or LISP),
\item accept 2 parameters $v_1$, $v_2$, which are vectors with the
exponents to be compared beginning with index 1
\item return
\[
\begin{array}{rll}
-1 & \mbox{ if } & v_1 \ll v_2 \\
0 & \mbox{ if } & v_1 = v_2 \\
+1 & \mbox{ if } & v_1 \gg v_2
\end{array}
\]
\end{itemize}
This procedure should be compiled because it is called very frequently.
Operators for fast vector access and fast integer arithmetic should be
used where available. A simple specimen for this procedure is:
\begin{center}
\begin{tabular}{l}
\hspace*{-1cm}symbolic procedure specimen $(v_1,v_2)$;
\vspace*{1mm}\\
\% simulating a 2 dim {\it lex} ordering. \\
if $getv(v1,1) < getv(v2,1)$ then $-1$ else \\
if $getv(v1,1) > getv(v2,1)$ then $1$ else \\
if $getv(v1,2) < getv(v2,2)$ then $-1$ else \\
if $getv(v1,2) > getv(v2,2)$ then $1$ else 0; \vspace*{2mm} \\
\hspace*{-1cm}torder private, specimen;
\end{tabular}
\end{center}
where e.g. with PSL-based REDUCE {\it getv} should be replaced by {\it
igetv} and $\#>$ resp $\#<$ should be used instead of the generic
comparisons.
During initialization, the Groebner package tests if the procedure
represents an admissible ordering. However, this test cannot be
complete and so the responsibility remains with the user.
% Chapter 4
\section{Decomposition of Ideals and Solving of Systems of
Equations} Based on the elementary Groebner 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 Groebner Bases}
% Subsection 4.1.1
\subsubsection{GROESOLVE: Solution of a Set of Polynomial
Equations} The GROESOLVE operator incorporates a macro algorithm;
lexical Groebner 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.
\subsubsection*{Example (intersections of a line with a circle):}
\[
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 Groebner Basis}
In many cases, it is difficult to do the general Groebner processing.
If a Groebner 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} Groebner
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}
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$ 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 [,\{var1,
\ldots , varn\}]); \]
where $\{exp1, exp2, \ldots , expm\}$ is a list of any number of
expressions or equations, {\it exp} is a single expression or equation
and $\{var1, var2, \ldots , varn\}$ is an optional list of variables.
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 Groebner basis. As long as the switch
GROEBIDQBASIS is on (default), the result is the Groebner basis of
the quotient. With OFF GROEBIDQBASIS, the final Groebner basis
calculation is suppressed; that makes sense, if e.g. a chain of
quotients has to be calculated and the time for the additional
normalizations should be saved; the result then is a basis for the
quotient, which, however, in general does not have the Groebner
properties.
% Section 4.2
\subsection{Operators for Groebner Bases in all Term Orderings}
In some cases where no Groebner
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. % Subsection 4.2.1
\subsubsection{HILBERTPOLYNOMIAL: Hilbert Polynomial of an
Ideal}
This algorithm was contributed by {\sc Joachim Hollman}, Royal
Institute of Technology, Stockholm (private communication).
\[
HILBERTPOLYNOMIAL (\{exp1, \ldots , expm\}
[,\{var1, \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.
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
Groebner 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
Groebner basis. So if a subsequent Hilbert calculation is planned, the
Groebner 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 the explicit calculation with
polynomials in a distributive representation on the REDUCE top level.
So they allow one to do Groebner 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}
\[
GSORT (p[,\{var1, var2, \ldots , varm\}]);
\]
where $p$ is a polynomial or a list of polynomials, $\{var1, var2,
\ldots , varm\}$ in the optional list of variables.
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.
\subsubsection*{Example:}
{\it korder alpha,beta,gamma;}\\
{\it dip} := {\it gsort$($gamma$*($alpha$-1)**\,2
*($beta$+1)**\,2)$;}
%{\small
\begin{verbatim}
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}
\[
GSPLIT (p[,\{var1, var2,\ldots ,varm\}]);
\]
where $p$ is a polynomial, $\{var1, var2, \ldots , varm\}$ in the
optional list of variables.
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.
\subsubsection*{Example:}
{\it gsplit(dip); }
%{\small
\begin{verbatim}
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}
%}
% Section 5.3
\subsection{Calculation of Buchberger's S-polynomial}
\[
GSPOLY (p1,p2[,\{var1, var2, \ldots , varm\}]);
\]
where $p1$ and $p2$ are polynomials, $\{var1, var2, \ldots ,
varm\}$ in the optional list of variables.
GSPOLY calculates the $S$-polynomial from $p1$ and $p2$;
Example for a complete calculation (taken from {\sc Davenport et al.}
\cite{DAST88}):
\hspace*{+1cm}{\it \% initial system} \\
\hspace*{+1cm}{\it korder x,y,z; torder lex;} \\
\hspace*{+1cm} $g1 := x**3*y*z - x*z**2;$\\
\hspace*{+1cm} $g2 := x*y**2*z - x*y*z; $ \\
\hspace*{+1cm} $g3 := x**2*y**2 - z;$
\hspace*{+1cm}{\it \% first S-polynomial} \\
\hspace*{+1cm} $g4 := gspoly(g2,g3);$
%{\small
\begin{verbatim}
2 2
G4 := X *Y*Z - Z
\end{verbatim}
%}
\hspace*{+1cm}{\it \% next S-polynomial} \\
\hspace*{+1cm} $p := gspoly(g2,g4); $
%{\small
\begin{verbatim}
2 2
P := X *Y*Z - Y*Z
\end{verbatim}
%}
\hspace*{+1cm}{\it \% and reducing, here only by g4, but preduce
needs a list} \\ \hspace*{+1cm} $g5 := preduce(p,\{g4\}); $
%{\small
\begin{verbatim}
2 2
G5 := - Y*Z + Z
\end{verbatim}
%}
\hspace*{+1cm}{\it \% last S-polynomial} \\
\hspace*{+1cm}$ g6 := gspoly(g4,g5);$
%{\small
\begin{verbatim}
2 2 3
G6 := X *Z - Z
\end{verbatim}
%}
\hspace*{+1cm}{\it \% and the final basis sorted descending} \\
\hspace*{+1cm}{\it gsort} $(\{g2,g3,g4,g5,g6\});$
%{\small
\begin{verbatim}
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}
%}
\newpage
%\section{References}
\addcontentsline{toc}{section}{References}
\begin{thebibliography}{99}
\bibitem {BOGEK86} W. Boege, R. Gebauer, R., H. Kredel.: {\it Some
Examples for Solving Systems of Algebraic Equations by Calculating
Groebner Bases}. J. Symbolic Computation~1, pp.~83-98, (1986).
\bibitem {BUCH85} B. Buchberger: {\it Groebner Bases: An
Algorithmic Method in Polynomial Ideal Theory}. In: (Bose, N. K. ed.)
Progress, directions and open problems in multidimensional
systems theory. pp.~184-232. Dordrecht: Reidel, (1985).
\bibitem {BUCH88} B.~Buchberger: {\it Applications of Groebner
Bases in Non-Linear Computational Geometry}. In: (Janssen, R. ed.)
Trends in Computer Algebra, pp.~52-80. Berlin,
Heidelberg (1988).
\bibitem {DAST88} J. H. Davenport, Y. Siret, E. Tournier: {\it
Computer Algebra, Systems and Algorithms for Algebraic
Computation}, London (1988).
\bibitem {EDJ81} K. H. Ebert, P. Deuflhard, W. Jaeger (ed.): {\it
Modelling of Chemical Reaction Systems}. Springer Ser. Chem. Phys.
18 (1981).
\bibitem{FGLM} J. C. Faug{\`e}re, P. Gianni, D. Lazard, T. Mora: {\it
Efficient Computation of Zero-Dimensional Groebner Bases by Change
of Ordering.} Preprint (1989).
\bibitem {GEMO88} R. Gebauer, H. M. M\"oller: {\it On an
Installation of Buchberger's Algorithm}. J. Symbol.
Computation, Vol. 6, pp.~275-286 (1988).
\bibitem {KRED88} H. Kredel: {\it Admissible Termorderings Used in
Computer Algebra Systems}. SIGSAM Bulletin, Vol. 22, 1 (1988).
\bibitem {MEMON88} H. Melenk, H. M. M\"oller, W. Neun : {\it On
Groeber Bases Computation on a Supercomputer Using REDUCE}.
Konrad-Zuse-Zentrum f\"ur Infor\-ma\-tions\-technik Berlin, SC
88-2 (January 1988).
\end{thebibliography}
\end{document}