doc/manual2/groebner.tex

\chapter{GROEBNER: A Gr\"obner basis package}
\label{GROEBNER}
\typeout{{GROEBNER: A Gr\"obner basis package}}

{\footnotesize
\begin{center}
Herbert Melenk \& Winfried Neun \\
Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\
Takustra\"se 7 \\
D--14195 Berlin--Dahlem, Germany \\[0.05in]
e--mail:  melenk@zib.de \\[0.05in]
and \\[0.05in]
H.M. M\"oller \\
Fernuniversit\"at Hagen FB Math und Informatik\\
Postfach 940 \\
D--58084 Hagen, Germany\\[0.05in]
e--mail: Michael.Moeller@fernuni-hagen.de
\end{center}
}

\ttindex{GROEBNER}

Gr\"obner bases are a valuable tool for solving problems in
connection with multivariate polynomials, such as solving systems of
algebraic equations and analysing polynomial ideals.

\index{GROEBNER package}\index{Buchberger's Algorithm}
The GROEBNER package calculates Gr\"obner bases using the
Buchberger algorithm.  It can be used over a variety of different
coefficient domains, and for different variable and term orderings.

\section{}
\subsection{Term Ordering} \par
In the theory of Gr\"obner bases, the terms of polynomials are
considered as ordered.  Several order modes are available in
the current package, including the basic modes:
\index{LEX ! term order}\index{GRADLEX ! term order}
\index{REVGRADLEX ! term order}

\begin{center}
LEX, GRADLEX, REVGRADLEX
\end{center}

All orderings are based on an ordering among the variables.  For each
pair of variables $(a,b)$ an order relation must be defined, {\em
e.g.\ } ``$ a\gg b $''.  The greater sign $\gg$  does not represent a
numerical relation among the variables; it can be interpreted only in
terms of formula representation: ``$a$'' will be placed in front of
``$b$'' or ``$a$''  is more complicated than ``$b$''.

The sequence of variables constitutes this order base.  So the notion
of
\[
\{x1,x2,x3\}
\]

as a list of variables at the same time means
\[
x1 \gg x2 \gg x3
\]
with respect to the term order.

If terms (products of powers of variables) are compared with LEX,
that term is chosen which has a greater variable or a higher degree
if the greatest variable is the first in both.  With GRADLEX the sum of
all exponents (the total degree) is compared first, and if that does
not lead to a decision, the LEX method is taken for the final decision.
The REVGRADLEX method also compares the total degree first, but
afterward it uses the LEX method in the reverse direction; this is the
method originally used by Buchberger.
Note that the LEX ordering is identical to the standard \REDUCE{}
kernel ordering, when KORDER is set explicitly to the sequence of
variables.

\index{default ! term order}
LEX is the default term order mode in the GROEBNER package.

\section{The Basic Operators}
\subsection{Term Ordering Mode}

\begin{description}
\ttindex{TORDER}
\item [{\it TORDER}]($vl$,$m$,$[p_1,p_2,\ldots]$);

where $vl$ is a variable list (or the empty list if
no variables are declared explicitly),
$m$ is the name of a term ordering mode LEX, GRADLEX,
REV\-GRAD\-LEX (or another implemented mode) and
$[p_1,p_2,\ldots]$ are additional parameters for the
term ordering mode (not needed for the basic modes).

TORDER sets variable set and the term ordering mode.
The default mode is LEX.  The previous description is returned
as a list with corresponding elements.  Such a list can
alternatively passed as sole argument to TORDER.

If the variable list is empty or if the TORDER declaration
is omitted, the automatic variable extraction is activated.

\ttindex{GVARS}
\item[{\it GVARS}] ({\it\{exp$1$, exp$2$, $ \ldots$, exp$n$\}});

 where $\{exp1, exp2, \ldots , expn\}$ is a list of expressions or
equations.

GVARS extracts from the expressions $\{exp1, exp2, \ldots , expn\}$
the kernels, which can play the role of variables for a Gr\"obner
calculation.  This can be used {\em e.g.\ } in a TORDER declaration.
\end{description}

\subsection{GROEBNER: Calculation of a Gr\"obner Basis}
\begin{description}
\ttindex{GROEBNER}
\item[{\it GROEBNER}] $\{exp1, exp2, \ldots , expm\}; $

where $\{exp1, exp2, \ldots , expm\}$ is a list of
expressions or equations.

GROEBNER calculates the Gr\"obner basis of the given set of
expressions with respect to the current TORDER setting.

The Gr\"obner basis $\{1\}$ means that the ideal generated by the
input polynomials is the whole polynomial ring, or equivalently, that
the input polynomials have no zeros in common.

As a side effect, the sequence of variables is stored as a \REDUCE\ list
in the shared variable \ttindex{gvarslast}{\tt gvarslast}.
\end{description}

\example \index{GROEBNER package ! example}
\begin{verbatim}
   torder({},lex)$
   groebner{3*x**2*y + 2*x*y + y + 9*x**2 + 5*x - 3,
   2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x + 3,
   x**3*y + x**2*y + 3*x**3 + 2*x**2 };

               2
     {8*X - 2*Y  + 5*Y + 3,

         3      2
      2*Y  - 3*Y  - 16*Y + 21}
\end{verbatim}


The operation of GROEBNER can be controlled by the following
switches:
\begin{description}
\ttindex{GROEBOPT}
\item[GROEBOPT] -- If set ON, the sequence of variables is optimized
with respect to execution speed; note that the final list of variables
is available in\ttindex{GVARSLAST} GVARSLAST.

An explicitly declared dependency supersedes the
variable optimization.
By default GROEBOPT is off, conserving the original variable
sequence.

\ttindex{GROEBFULLREDUCTION}
\item[GROEBFULLREDUCTION] -- If set off, the reduction steps during
the \linebreak[4] GROEBNER operation are limited to the pure head
term reduction; subsequent terms are reduced otherwise.
By default GROEBFULLREDUCTION is on.

\ttindex{GLTBASIS}
\item[GLTBASIS] -- If set on, the leading terms of the result basis are
extracted.  They are collected in a basis of monomials, which is
available as value of the global variable with the name GLTB.

\end{description}

\subsection{GZERODIM?: Test of $\dim = 0$}
\begin{description}
\ttindex{GZERODIM?}
\item[{\it GZERODIM}!?] $bas$ \\
where {\it bas} is a Gr\"obner basis in the current setting.
The result is {\it NIL}, if {\it bas} is the basis of an ideal of
polynomials with more than finitely many common zeros.
If the ideal is zero dimensional, {\em i.e.\ } the polynomials of the
ideal have only finitely many zeros in common, the result is an
integer $k$ which is the number of these common zeros (counted with
multiplicities).
\end{description}

\subsection{GDIMENSION, GINDEPENDENT\_SETS}
The following operators can be used to compute the dimension
and the independent variable sets of an ideal which has the
Gr\"obner basis {\it bas} with arbitrary term order:
\begin{description}
\ttindex{GDIMENSION}\ttindex{GINDEPENDENT\_SETS}
\ttindex{ideal dimension}\ttindex{independent sets}
\item[Gdimension]$bas$
\item[Gindependent\_sets]$bas$
{\it Gindependent\_sets} computes the maximal
left independent variable sets of the ideal, that are
the variable sets which play the role of free parameters in the
current ideal basis.  Each set is a list which is a subset of the
variable list.  The result is a list of these sets.  For an
ideal with dimension zero the list is empty.
{\it GDimension} computes the dimension of the ideal,
which is the maximum length of the independent sets.
\end{description}

\subsection{GLEXCONVERT: Conversion to a Lexical Base}
\begin{description}
\ttindex{GLEXCONVERT}
\item[{\it GLEXCONVERT}] $ \left(\{exp,\ldots , expm\} \left[,\{var1
\ldots , varn\}\right]\right.$ \\
$\left. \left[,MAXDEG=mx\right] \left[,NEWVARS=\{nv1, \ldots , nvk\}\right]\right) $ \\
where $\{exp1, \ldots , expm\}$ is a Gr\"obner basis with
$\{var1, \ldots , varn\}$ as variables in the current term order mode,
$mx$ is an integer, and
$\{nv1, \ldots , nvk\}$ is a subset of the basis variables.
For this operator the source and target variable sets must be specified
explicitly.
\end{description}

GLEXCONVERT converts a basis of a zero-dimensional ideal (finite number
of isolated solutions) from arbitrary ordering into a basis under {\it
lex} ordering.  During the call of GLEXCONVERT the original ordering of
the input basis must be still active.

NEWVARS defines the new variable sequence.  If omitted, the
original variable sequence is used.   If only a subset of variables is
specified here, the partial ideal basis is evaluated.  For the
calculation of a univariate polynomial, NEW\-VARS should be a list
with one element.

MAXDEG is an upper limit for the degrees.  The algorithm stops with
an error message, if this limit is reached.

A warning occurs if the ideal is not zero dimensional.

GLEXCONVERT is an implementation of the FLGM algorithm.   Often, the
calculation of a Gr\"obner basis
with a graded ordering and subsequent conversion to {\it lex} is
faster than a direct {\it lex} calculation.   Additionally, GLEXCONVERT
can be used to transform a {\it lex} basis into one with different
variable sequence, and it supports the calculation of a univariate
polynomial.  If the latter exists, the algorithm is even applicable in
the non zero-dimensional case, if such a polynomial exists.

\begin{verbatim}
   torder({{w,p,z,t,s,b},gradlex)

   g  :=  groebner  { f1 := 45*p + 35*s -165*b -36,
         35*p + 40*z + 25*t - 27*s, 15*w + 25*p*s +30*z -18*t
        -165*b**2, -9*w + 15*p*t  + 20*z*s,
        w*p + 2*z*t - 11*b**3, 99*w - 11*s*b +3*b**2,
        b**2 + 33/50*b + 2673/10000};

  G := {60000*W + 9500*B + 3969,

      1800*P - 3100*B - 1377,

      18000*Z + 24500*B + 10287,

      750*T - 1850*B + 81,

      200*S - 500*B - 9,
             2
      10000*B  + 6600*B + 2673}

   glexconvert(g,{w,p,z,t,s,b},maxdeg=5,newvars={w});

               2
    100000000*W  + 2780000*W + 416421

   glexconvert(g,{w,p,z,t,s,b},maxdeg=5,newvars={p});

          2
    6000*P  - 2360*P + 3051

\end{verbatim}

\subsection{GROEBNERF: Factorizing Gr\"obner Bases}

If Gr\"obner bases are computed in order to solve systems of equations
or to find the common roots of systems of polynomials, the factorizing
version of the Buchberger algorithm can be used.  The theoretical
background is simple: if a polynomial $p$ can be represented as a
product of two (or more) polynomials, {\em e.g.\ } $h= f*g$, then $h$
vanishes if and only if one of the factors vanishes.  So if during the
calculation of a Gr\"obner basis $h$ of the above form is detected,
the whole problem can be split into two (or more) disjoint branches.
Each of the branches is simpler than the complete problem; this saves
computing time and space.  The result of this type of computation is a
list of (partial) Gr\"obner bases; the solution set of the original
problem is the union of the solutions of the partial problems,
ignoring the multiplicity of an individual solution.  If a branch
results in a basis $\{1\}$, then there is no common zero, {\em i.e.\ }no
additional solution for the original problem, contributed by this
branch.

\subsubsection{GROEBNERF Call}
\ttindex{GROEBNERF}
The syntax of GROEBNERF is the same as for GROEBNER.
\[
\mbox{\it GROEBNERF}(\{exp1, exp2, \ldots , expm\}
         [,\{\},\{nz1, \ldots nzk\});
\]
where $\{exp1, exp2, \ldots , expm\} $ is a given list of expressions or
equations, and $\{nz1, \ldots nzk\}$ is
an optional list of polynomials known to be non-zero.

GROEBNERF tries to separate polynomials into individual factors and
to branch the computation in a recursive manner (factorisation tree).
The result is a list of partial Gr\"obner bases.  If no factorisation can
be found or if all branches but one lead to the trivial basis $\{1\}$,
the result has only one basis; nevertheless it is a list of lists of
polynomials.  If no solution is found, the result will be $\{\{1\}\}$.
Multiplicities (one factor with a higher power, the same partial basis
twice) are deleted as early as possible in order to speed up the
calculation.  The factorising is controlled by some switches.

As a side effect, the sequence of variables is stored as a \REDUCE\ list in
the shared variable
\begin{center}
gvarslast .
\end{center}
If GLTBASIS is on, a corresponding list of leading term bases is
also produced and is available in the variable GLTB.

The third parameter of GROEBNERF allows one to declare some polynomials
nonzero.  If any of these is found in a branch of the calculation
the branch is cancelled.  This can be used to save a substantial amount
of computing time.  The second parameter must be included as an
empty list if the third parameter is to be used.

\begin{verbatim}
   torder({x,y},lex)$
   groebnerf { 3*x**2*y + 2*x*y + y + 9*x**2 + 5*x = 3,
               2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x = -3,
                x**3*y + x**2*y + 3*x**3 + 2*x**2 };


       {{Y - 3,X},

                      2
    {2*Y + 2*X - 1,2*X  - 5*X - 5}}
\end{verbatim}
%}

It is obvious here that the solutions of the equations can be read
off immediately.

All switches from GROEBNER are valid for GROEBNERF as well:
\ttindex{GROEBOPT} \ttindex{GLTBASIS}
\ttindex{GROEBFULLREDUCTION}\ttindex{GROEBSTAT}\ttindex{TRGROEB}
\ttindex{TRGROEBS}\ttindex{TRGROEB1}
\begin{center}
\begin{tabular}{l}
GROEBOPT \\
GLTBASIS \\
GROEBFULLREDUCTION \\
GROEBSTAT \\
TRGROEB \\
TRGROEBS \\
TRGROEB1
\end{tabular}
\end{center}

\subsubsection{Restriction of the Solution Space}
In some applications only a subset of the complete solution set
of a given set of equations is relevant, {\em e.g.\ }  only
nonnegative values or positive definite values for the variables.
A significant amount of computing time can be saved if
nonrelevant computation branches can be terminated early.

Positivity: If a polynomial has no (strictly) positive zero, then
every system containing it has no nonnegative or strictly positive
solution.  Therefore, the Buchberger algorithm tests the coefficients of
the polynomials for equal sign if requested.  For example, in $13*x +
15*y*z $ can be zero with real nonnegative values for $x, y$ and $z$
only if $x=0$ and $y=0$ or $ z=0$; this is a sort of ``factorization by
restriction''.  A polynomial $13*x + 15*y*z + 20$ never can vanish
with nonnegative real variable values.

Zero point:  If any polynomial in an ideal has an absolute term, the ideal
cannot have the origin point as a common solution.

By setting the shared variable
\ttindex{GROEBRESTRICTION}
\begin{center} GROEBRESTRICTION \end{center}
GROEBNERF is informed of the type of restriction the user wants to
impose on the solutions:
\begin{center}
\begin{tabular}{l}
{\it GROEBRESTRICTION:=NONEGATIVE;} \\
\hspace*{+.5cm} only nonnegative real solutions are of
interest\vspace*{4mm} \\
{\it GROEBRESTRICTION:=POSITIVE;} \\
\hspace*{+.5cm}only nonnegative and nonzero solutions are of
interest\vspace*{4mm} \\
{\it GROEBRESTRICTION:=ZEROPOINT;} \\
\hspace*{+.5cm}only solution sets which contain the point
$\{0,0,\ldots,0\}$ are or interest.
\end{tabular}
\end{center}

If GROEBNERF detects a polynomial which formally conflicts with the
restriction, it either splits the calculation into separate branches, or,
if a violation of the restriction is determined, it cancels the actual
calculation branch.


\subsection{GREDUCE, PREDUCE: Reduction of Polynomials}

\subsubsection{Background} \label{GROEBNER:background}
Reduction of a polynomial ``p'' modulo a given sets of polynomials
``B'' is done by the reduction algorithm incorporated in the
Buchberger algorithm.

% Subsection 3.5.2
\subsubsection{Reduction via Gr\"obner Basis Calculation}
\ttindex{GREDUCE}
\[
\mbox{\it  GREDUCE}(exp, \{exp1, exp2, \ldots , expm\}]);
\]
where {\it exp} is an expression, and $\{exp1, exp2,\ldots , expm\}$ is
a list of any number of expressions or equations.

GREDUCE first converts the list of expressions $\{exp1, \ldots ,
expn\}$ to a Gr\"obner basis, and then reduces the given expression
modulo that basis.  An error results if the list of expressions is
inconsistent.  The returned value is an expression representing the
reduced polynomial.  As a side effect, GREDUCE sets the variable {\it
gvarslast} in the same manner as GROEBNER does.


\subsubsection{Reduction with Respect to Arbitrary Polynomials}
\ttindex{PREDUCE}
\[
 PREDUCE(exp, \{exp1, exp2,\ldots , expm\});
\]
where $ exp $  is an expression, and $\{exp1, exp2, \ldots ,
expm \}$ is a list of any number of expressions or equations.

PREDUCE reduces the given expression modulo the set $\{exp1,
\ldots , expm\}$.  If this set is a Gr\"obner basis, the obtained reduced
expression is uniquely determined.  If not, then it depends on the
subsequence of the single reduction steps
(see~\ref{GROEBNER:background}).  PREDUCE does not check whether
$\{exp1, exp2, \ldots , expm\}$ is a Gr\"obner basis in the actual
order.  Therefore, if the expressions are a Gr\"obner basis calculated
earlier with a variable sequence given explicitly or modified by
optimisation, the proper variable sequence and term order must
be activated first.

\example (PREDUCE called with a Gr\"obner basis):
\begin{verbatim}
  torder({x,y},lex);
  gb:=groebner{3*x**2*y + 2*x*y + y + 9*x**2 + 5*x - 3,
               2*x**3*y - x*y - y + 6*x**3 - 2*x**2 - 3*x + 3,
               x**3*y + x**2*y + 3*x**3 + 2*x**2}$
  preduce (5*y**2 + 2*x**2*y + 5/2*x*y + 3/2*y
             + 8*x**2 + 3/2*x - 9/2, gb);

      2
     Y
\end{verbatim}


\section{Ideal Decomposition \& Equation System Solving}
Based on the elementary Gr\"obner operations, the GROEBNER package offers
additional operators, which allow the decomposition of an ideal or of a
system of equations down to the individual solutions.  Details of the
operators\ttindex{GROESOLVE}\ttindex{GROEBNERF}
\ttindex{IDEALQUOTIENT}GROESOLVE, GROEBNERF and IDEALQUOTIENT can be
found in the full documentation, with associated functions.