reduce-historical/r38/packages/cgb/cgb.tex

% ----------------------------------------------------------------------
% $Id: cgb.tex,v 1.4 1999/04/13 22:23:22 sturm Exp $
% ----------------------------------------------------------------------
% Copyright (c) 1999 Andreas Dolzmann and Thomas Sturm
% ----------------------------------------------------------------------
% $Log: cgb.tex,v $
% Revision 1.4  1999/04/13 22:23:22  sturm
% Added remark on updates on the WWW page.
%
% Revision 1.3  1999/04/13 21:29:18  sturm
% Added documentation of switches.
% Recomputed examples.
%
% Revision 1.2  1999/04/11 13:26:29  sturm
% Readded documentation for switch cgbgen.
%
% Revision 1.1  1999/04/04 19:29:30  sturm
% Copied and overworked Rev. 1.3 of the old cgb version.
%
% ----------------------------------------------------------------------
\documentstyle{article}
\overfullrule2mm
\newcommand{\C}{{\bf C}}
\newcommand{\R}{{\bf R}}
\newcommand{\Id}{{\rm Id}}
\begin{document}
\title{CGB: Computing Comprehensive Gr\"obner Bases}
\author{Andreas Dolzmann \& Thomas Sturm\\
Department of Mathematics and Computer Science\\ University of Passau\\
D-94030 Passau, Germany\\[1ex]
e-mail: {\tt dolzmann@uni-passau.de}, {\tt sturm@uni-passau.de}\\[1ex]
and\\[1ex]
Winfried Neun\\
Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin\\
Takustra\ss{}e 7\\
D-14195 Berlin-Dahlem, Germany\\[1ex]
e-mail: {\tt neun@zib.de}}
\date{15 April 1999}
\maketitle

\section{Introduction}
Consider the ideal basis $F=\{ax,x+y\}$. Treating $a$ as a parameter,
the calling sequence
\begin{verbatim}
torder({x,y},lex)$
groebner{a*x,x+y};

  {x,y}
\end{verbatim}
yields $\{x,y\}$ as reduced Gr\"obner basis. This is, however, not
correct under the specialization $a=0$. The reduced Gr\"obner basis
would then be $\{x+y\}$. Taking these results together, we obtain
$C=\{x+y,ax,ay\}$, which is correct wrt.~{\em all} specializations for
$a$ including zero specializations. We call this set $C$ a {\em
comprehensive Gr\"obner basis} ({\sc cgb}).

The notion of a {\sc cgb} and a corresponding algorithm has been
introduced bei Weispfenning \cite{Weispfenning:92}. This algorithm
works by performing case distinctions wrt.~parametric coefficient
polynomials in order to find out what the head monomials are under all
possible specializations. It does thus not only determine a {\sc cgb},
but even classifies the contained polynomials wrt.~the specializations
they are relevant for. If we keep the Gr\"obner bases for all cases
separate and associate information on the respective specializations
with them, we obtain a {\em Gr\"obner system}. For our example, the
Gr\"obner system is the following;
$$
\left[
\begin{array}{c|c}
a\neq0 & \{x+y,ax,ay\}\\
a=0 & \{x+y\}
\end{array}
\right].
$$
A {\sc cgb} is obtained as the union of the single Gr\"obner bases in
a Gr\"obner system. It has also been shown that, on the other hand, a
Gr\"obner system can easily be reconstructed from a given {\sc cgb}
\cite{Weispfenning:92}.

The CGB package provides functions for computing both {\sc cgb}'s and
Gr\"obner systems, and for turning Gr\"obner systems into {\sc cgb}'s.
%
\section{Using the REDLOG Package}
For managing the conditions occurring with the {\sc cgb} computations,
the CGB package uses the package REDLOG implementing first-order
formulas, \cite{DolzmannSturm:97a,DolzmannSturm:99}, which is also
part of the \textsc{reduce} distribution.
%
\section{Term Ordering Mode}
The CGB package uses the settings made with the function {\tt torder}
of the GROEBNER package. This includes in particular the choice of the
main variables. All variables not mentioned in the variable list
argument of {\tt torder} are parameters. The only term ordering modes
recognized by \textsc{cgb} are {\tt lex} and {\tt revgradlex}.
%
\section{CGB: Comprehensive Gr\"ob\-ner Basis}
The function {\tt cgb} expects a list $F$ of expressions. It returns a
{\sc cgb} of $F$ wrt.~the current {\tt torder} setting.
%
\subsection*{Example}
\begin{verbatim}
torder({x,y},lex)$
cgb{a*x+y,x+b*y};

{x + b*y,a*x + y,(a*b - 1)*y}

ws;

{b*y + x,

 a*x + y,

 y*(a*b - 1)}
\end{verbatim}
Note that the basis returned by the {\tt cgb} call has not undergone
the standard evaluation process: The returned polynomials are ordered
wrt.~the chosen term order. Reevaluation changes this as can be seen
with the output of {\tt ws}.
%
\section{GSYS: Gr\"obner System}
The function {\tt gsys} follows the same calling conventions as {\tt
cgb}. It returns the complete Gr\"obner system represented as a nested
list
\begin{center}
\begin{tt}
$\bigl\{\bigl\{c_1,\{g_{11},\ldots,g_{1n_1}\}\bigr\},\dots,
\bigl\{c_m,\{g_{m1},\dots,g_{1n_m}\}\bigr\}\bigr\}$.
\end{tt}
\end{center}
The {\tt $c_i$} are conditions in the parameters represented as
quantifier-free REDLOG formulas. Each choice of parameters will obey
at least one of the {\tt $c_i$}. Whenever a choice of parameters obeys
some {\tt $c_i$}, the corresponding {\tt $\{g_{i1},\ldots,g_{in_i}\}$}
is a Gr\"obner basis for this choice.
%
\subsection*{Example}
\begin{verbatim}
torder({x,y},lex)$
gsys {a*x+y,x+b*y};

{{a*b - 1 <> 0 and a <> 0,

  {a*x + y,x + b*y,(a*b - 1)*y}},

 {a <> 0 and a*b - 1 = 0,

  {a*x + y,x + b*y}},

 {a = 0,{a*x + y,x + b*y}}}
\end{verbatim}
As with the function {\tt cgb}, the contained polynomials remain
unevaluated.

Computing a Gr\"obner system is not harder than computing a {\sc cgb}.
In fact, {\tt cgb} also computes a Gr\"obner system and then turns it
into a {\sc cgb}.

\subsection{Switch CGBGEN: Only the Generic Case}
If the switch {\tt cgbgen} is turned on, both {\tt gsys} and {\tt
cgb} will assume all parametric coefficients to be non-zero ignoring
the other cases. For {\tt cgb} this means that the result equals---up
to auto-reduction---that of {\tt groebner}. A call to {\tt gsys} will
return this result as a single case including the assumptions made
during the computation:
%
\subsection*{Example}
\begin{verbatim}
torder({x,y},lex)$
on cgbgen;
gsys{a*x+y,x+b*y};

{{a*b - 1 <> 0 and a <> 0,

  {a*x + y,x + b*y,(a*b - 1)*y}}}

off cgbgen;
\end{verbatim}
%
\section{GSYS2CGB: Gr\"obner System to CGB}
The call {\tt gsys2cgb} turns a given Gr\"obner system into a {\sc
cgb} by constructing the union of the Gr\"obner bases of the single
cases.
%
\subsection*{Example}
\begin{verbatim}
torder({x,y},lex)$
gsys{a*x+y,x+b*y}$
gsys2cgb ws;

{x + b*y,a*x + y,(a*b - 1)*y}
\end{verbatim}
%
\section{Switch CGBREAL: Computing over the Real Numbers}\label{cgbreal}
All computations considered so far have taken place over the complex
numbers, more precisely, over algebraically closed fields. Over the
real numbers, certain branches of the {\sc cgb} computation can become
inconsitent though they are not inconsistent over the complex numbers.
Consider, e.g., a condition $a^2+1=0$.

When turning on the switch {\tt cgbreal}, all simplifications of conditions
are performed over the real numbers. The methods used for this are
described in \cite{DolzmannSturm:97c}.
%
\subsection*{Example}
\begin{verbatim}
torder({x,y},lex)$
off cgbreal;
gsys {a*x+y,x-a*y};

   2
{{a  + 1 <> 0 and a <> 0,

                     2
  {a*x + y,x - a*y,(a  + 1)*y}},

              2
 {a <> 0 and a  + 1 = 0,{a*x + y,x - a*y}},

 {a = 0,{a*x + y,x - a*y}}}

on cgbreal;
gsys({a*x+y,x-a*y});

{{a <> 0,

                     2
  {a*x + y,x - a*y,(a  + 1)*y}},

 {a = 0,{a*x + y,x - a*y}}}
\end{verbatim}

\section{Switches}
\begin{description}
\item[cgbreal] Compute over the real numbers. See
Section~\ref{cgbreal} for details.

\item[cgbgs] Gr\"obner simplification of the condition. The switch
{\tt cgbgs} can be turned on for applying advanced algebraic
simplification techniques to the conditions. This will, in general,
slow down the computation, but lead to a simpler Gr\"obner system.

\item[cgbstat] Statistics of the CGB run. The switch {\tt cgbstat}
toggles the creation and output of statistical information on the CGB
run. The statistical information is printed at the end of the run.

\item[cgbfullred] Full reduction. By default, the CGB functions
perform full reductions in contrast to pure top reductions. By turning
off the switch {\tt cgbfullred}, reduction can be restricted to top
reductions.
\end{description}

\section{Updates}
Information on and updates of the CGB package will be provided on

\centerline{{\tt http://www.fmi.uni-passau.de/\char126 reduce/}.}

\bibliographystyle{alpha}
\bibliography{cgb}
\end{document}