reduce-historical/r38/doc/manual2/xideal.tex

\chapter{XIDEAL: Gr\"obner for exterior algebra}
\label{XIDEAL}
\typeout{{XIDEAL: Gr\"obner Bases for exterior algebra}}

{\footnotesize
\begin{center}
David Hartley \\
GMD, Institute I1, Schloss Birlinghoven \\
D--53757 St. Augustin, Germany \\[0.05in]
e--mail: David.Hartley@gmd.de \\[0.1in]
and \\
Philip A.~Tuckey \\
Max Planck Institute for Physics \\
Foehringer Ring 6 \\
D--80805 Munich, Germany \\[0.05in]
e--mail: pht@iws170.mppmu.mpg.de
\end{center}
}
\ttindex{XIDEAL}

XIDEAL extends the Gr\"obner base method to exterior algebras.

XIDEAL constructs Gr\"obner bases for solving the left ideal membership
problem: Gr\"obner left ideal bases or GLIBs. For graded ideals, where each
form is homogeneous in degree, the distinction between left and right
ideals vanishes.  Furthermore, if the generating forms are all homogeneous,
then the Gr\"obner bases for the non-graded and graded ideals are
identical.  In this case, XIDEAL is able to save time by truncating the
Gr\"obner basis at some maximum degree if desired.
XIDEAL uses the EXCALC package (chapter~\ref{EXCALC}).

\section{Operators}

\subsubsection*{XIDEAL}

\f{XIDEAL} calculates a Gr\"obner left ideal basis in
an exterior algebra. The syntax is\ttindex{XIDEAL}
\begin{verbatim}
     XIDEAL(S:list of forms[,R:integer]):list of forms.
\end{verbatim}
\f{XIDEAL} calculates the Gr\"obner left ideal basis for the left ideal
generated by \f{S} using graded lexicographical ordering based on the
current kernel ordering.  The resulting list can be used for subsequent
reductions with \f{XMODULOP} as long as the kernel ordering is not
changed.  If the set of generators \f{S} is graded, an optional parameter
\f{R} can be given, and \f{XIDEAL} produces a truncated basis suitable for
reducing exterior forms of degree less than or equal to \f{R} in the left
ideal.  This can save time and space with large expressions, but the result
cannot be used for exterior forms of degree greater than \f{R}.  See also
the switches \f{XSTATS} and \f{XFULLREDUCTION}.


\subsubsection*{XMODULO}

\f{XMODULO} reduces exterior forms to their (unique) normal forms modulo a
left ideal. The syntax is\ttindex{XMODULO}
\begin{verbatim}
     XMODULO(F:form, S:list of forms):form
\end{verbatim}
or
\begin{verbatim}
     XMODULO(F:list of forms, S:list of forms):list of forms.
\end{verbatim}
An alternative infix syntax is also available:
\begin{verbatim}
     F XMODULO S.
\end{verbatim}
\f{XMODULO(F,S)} first calculates a Gr\"obner basis for the left ideal
generated by \f{S}, and then reduces \f{F}.  \f{F} may be either a single
exterior form, or a list of forms, and \f{S} is a list of forms.  If \f{F}
is a list of forms, each element is reduced, and any which vanish are
deleted from the result.  If this operator is used more than once, and
\f{S} does not change between calls, then the Gr\"obner basis is not
recalculated.  If the set of generators \f{S} is graded, then a truncated
Gr\"obner basis is calculated using the degree of \f{F} (or the maximal
degree in \f{F}).

\subsubsection*{XMODULOP}

\f{XMODULOP} reduces exterior forms to their (not necessarily unique)
normal forms modulo a set of exterior polynomials. The syntax
is\ttindex{XMODULOP}
\begin{verbatim}
     XMODULOP(F:form, S:list of forms):form
\end{verbatim}
or
\begin{verbatim}
     XMODULOP(F:list of forms, S:list of forms):list of forms.
\end{verbatim}
An alternative infix syntax is also available:
\begin{verbatim}
     F XMODULOP S.
\end{verbatim}
\f{XMODULOP(F,S)} reduces \f{F} with respect to the set of exterior
polynomials \f{S}, which is not necessarily a Gr\"obner basis. \f{F} may be
either a single exterior form, or a list of forms, and \f{S} is a list of
forms. This operator can be used in conjunction with \f{XIDEAL} to produce
the same effect as \f{XMODULO}: for a single form \f{F} in an ideal
generated by the graded set \f{S}, \f{F XMODULO S} is equivalent to \f{F
XMODULOP XIDEAL(S,EXDEGREE F)}.


\section{Switches} 

\subsubsection*{XFULLREDUCE}

\f{ON XFULLREDUCE}\ttindex{XFULLREDUCE} allows \f{XIDEAL} and
\f{XMODULO} to calculate reduced (but not necessarily normed)
Gr\"obner bases, which speeds up subsequent reductions, and guarantees
a unique form (up to scaling) for the Gr\"obner basis.  \f{OFF
XFULLREDUCE} turns of this feature, which may speed up calculation of
the Gr\"obner basis.  \f{XFULLREDUCE} is \f{ON} by default. 


\subsubsection*{XSTATS}

\f{ON XSTATS}\ttindex{XSTATS} produces counting and timing
information.  As \f{XIDEAL} is running, a hash mark (\verb.#.) is
printed for each form taken from the input list, followed by a
sequences of carets (\verb.^.) and dollar signs (\verb.$.). Each caret
represents a new basis element obtained by a simple wedge product, and
each dollar sign represents a new basis element obtained from an
S-polynomial.  At the end, a table is printed summarising the
calculation.  \f{XSTATS} is \f{OFF} by default. 

\section{Examples}

Suppose EXCALC and XIDEAL have been loaded, the switches are at their
default settings, and the following exterior variables have been declared:

\begin{verbatim}
     pform x=0,y=0,z=0,t=0,f(i)=1,h=0,hx=0,ht=0;
\end{verbatim}

In a commutative polynomial ring, a single polynomial is its own Gr\"obner
basis.  This is no longer true for exterior algebras because of the presence
of zero divisors, and can lead to some surprising reductions:
\begin{verbatim}
     xideal {d x^d y - d z^d t};

          {d T^d Z + d X^d Y,

           d X^d Y^d Z,

           d T^d X^d Y}

     f(3)^f(4)^f(5)^f(6) 
       xmodulo {f(1)^f(2) + f(3)^f(4) + f(5)^f(6)};

          0
\end{verbatim}

The heat equation, $h_{xx}=h_t$ can be represented by the following
exterior differential system. 
\begin{verbatim}
     S := {d h - ht*d t - hx*d x,
           d ht^d t + d hx^d x,
           d hx^d t - ht*d x^d t};
\end{verbatim}
\f{XMODULO} can be used to check that the exterior differential system is
closed under exterior differentiation.
\begin{verbatim}
     d S xmodulo S;

          {}
\end{verbatim}

Non-graded left and right ideals are no longer the same:
\begin{verbatim}
     d t^(d z+d x^d y) xmodulo {d z+d x^d y};

          0

     (d z+d x^d y)^d t xmodulo {d z+d x^d y};

           - 2*d t^d z
\end{verbatim}
Higher order forms can now reduce lower order ones:
\begin{verbatim}
     d x xmodulo {d y^d z + d x,d x^d y + d z};

          0
\end{verbatim}
Any form containing a 0-form term generates the whole ideal:
\begin{verbatim}
     xideal {1 + f(1) + f(1)^f(2) + f(2)^f(3)^f(4)};

          {1}
\end{verbatim}