\chapter{CGB: Comprehensive Gr\"obner Bases}
\label{CGB}
\typeout{{CGB: Comprehensive Gr\"obner Bases}}
{\footnotesize
\begin{center}
Andreas Dolzmann \& Thomas Sturm\\
Department of Mathematics and Computer Science\\ University of Passau\\
D-94030 Passau, Germany\\[1ex]
e-mail: dolzmann@uni-passau.de, sturm@uni-passau.de
\end{center}
}
\ttindex{REDLOG}
\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 \f{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 \f{TORDER} are parameters. The only term ordering modes
recognized by \textsc{cgb} are \f{LEX} and \f{REVGRADLEX}.
%
\section{CGB: Comprehensive Gr\"ob\-ner Basis}
The function \f{CGB}\ttindex{CGB} expects a list $F$ of expressions.
It returns a {\sc cgb} of $F$ wrt.~the current \f{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 \f{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 \f{WS}.
%
\section{GSYS: Gr\"obner System}
The function \f{GSYS}\ttindex{GSYS} follows the same calling conventions as
\f{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 \f{CGB}, the contained polynomials remain
unevaluated.
Computing a Gr\"obner system is not harder than computing a {\sc cgb}.
In fact, \f{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 \f{CGBGEN}\ttindex{CGBGEN} is turned on, both \f{GSYS} and
\f{CGB} will assume all parametric coefficients to be non-zero ignoring
the other cases. For \f{CGB} this means that the result equals---up
to auto-reduction---that of \f{GROEBNER}. A call to \f{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 \f{GSYS2CGB}\ttindex{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 \f{CGBREAL}\ttindex{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[\f{CGBREAL}] Compute over the real numbers. See
Section~\ref{cgbreal} for details.
\item[\f{CGBGS}\ttindex{CGBGS}] Gr\"obner simplification of the condition. The switch
\f{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[\f{CGBSTAT}\ttindex{CGBSTAT}] Statistics of the CGB run. The switch \f{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[\f{CGBFULLRED}\ttindex{CGBFULLRED}] Full reduction. By default, the CGB functions
perform full reductions in contrast to pure top reductions. By turning
off the switch \f{CGBFULLRED}, reduction can be restricted to top
reductions.
\end{description}