reduce-historical/r36/doc/XIDEAL.TEX

\documentstyle[11pt,reduce]{article}

\title{\bf XIDEAL\\
Gr\"obner Bases for Exterior Algebra}

\author{
David Hartley\thanks{email: David.Hartley@gmd.de}       \\
GMD, Institute I1                                       \\
Schloss Birlinghoven                                    \\
D--53757 St. Augustin                                   \\
Germany                                                 \\
\and
Philip A.~Tuckey\thanks{email: pht@iws170.mppmu.mpg.de} \\
Max Planck Institute for Physics                        \\
Foehringer Ring 6                                       \\
D--80805 Munich                                         \\
Germany                                                 \\
}

\date{14th March 1994}

\begin{document}
\maketitle

\section{Description}

The method of Gr\"obner bases in commutative polynomial rings introduced by
Buchberger (e.g.~\cite{Buchberger}) is a well-known and very important tool
in polynomial ideal theory, for example in solving the ideal membership
problem. XIDEAL extends the method to exterior algebras using
algorithms from \cite{HT}.

There are two main departures from the commutative polynomial case. First,
owing to the non-commutative product in exterior algebras, ideals are no
longer automatically two-sided, and it is necessary to distinguish between
left and right ideals. Secondly, because there are zero divisors, confluent
reduction relations are no longer sufficient to solve the ideal membership
problem: a unique normal form for every polynomial does not guarantee that
all elements in the ideal reduce to zero. This leads to two possible
definitions of Gr\"obner bases as pointed out by Stokes \cite{Stokes}.

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 exterior calculus package EXCALC of E.~Schr\"ufer
\cite{EXCALC} to provide the exterior algebra definitions. EXCALC must be
loaded before XIDEAL will work. The basis 1-forms for the exterior algebra
are automatically extracted from the input. Consequently, each expression
must be written in terms of these 1-forms -- $p$-form kernels with $p>1$
are not allowed. Similarly all distinct 1-forms in the input are assumed to
be linearly independent -- if a dimension has been fixed (using the EXCALC
\f{SPACEDIM} or \f{COFRAME} statements), then input containing more than this
number of distinct 1-forms will generate an error. The exterior algebra can
be based on either an abstract vector space or the cotangent space at some
fixed point on a manifold. Any functions or 0-forms are treated as constant
non-vanishing coefficients.

The term ordering used is the graded lexicographical ordering based on the
prevailing EXCALC kernel ordering for the basis 1-forms. This puts
highest degree first and then sorts terms of the same degree
lexicographically. The EXCALC kernel ordering can be changed with the
\REDUCE{} \f{KORDER} or EXCALC \f{FORDER} statements.


\section{Operators}

\subsubsection*{XIDEAL}

\f{XIDEAL} calculates a Gr\"obner left ideal basis in
an exterior algebra. The syntax is
\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
\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
\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)}.

%\subsubsection*{SUBFORM}
%
%\f{SUBFORM} extends the \f{SUB} operator from ordinary {\REDUCE} to perform
%substitutions for factors in exterior products. For example
%\begin{verbatim}
%     SUB(d X^d Y = 0, d X^d Y^d Z)         -> d X^d Y^d Z
%     SUBFORM(d X^d Y = 0, d X^d Y^d Z)     -> 0.
%\end{verbatim}
%Care must be taken that the left-hand sides of substitutions are kernels,
%eg. \verb.d X^d Y. is a kernel in the usual ordering, but  \verb.d Y^d X.
%isn't.


\section{Switches}

\subsubsection*{XFULLREDUCE}

\f{ON 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*{XGRADED}
%
%\f{ON XGRADED} tells \f{XIDEAL} and \f{XMODULO} that all exterior ideals
%under consideration are graded: consist of forms of homogeneous degree. In
%this case, there is no distinction between left, right and two-sided
%ideals, and it is possible to truncate the calculation of Gr\"obner bases
%at the degree of the form or forms to be reduced. This saves considerable
%time and space. For non-graded ideals, \f{XGRADED} must be switched
%\f{OFF}. \f{XGRADED} is \f{ON} by default.

\subsubsection*{XSTATS}

\f{ON 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}


\begin{thebibliography}{M}

\bibitem{Buchberger}
        B.~Buchberger, {\em
        Gr\"obner Bases: an algorithmic method in polynomial ideal theory,}
        in {\em Multidimensional Systems Theory\/} ed.~N.K.~Bose
        (Reidel, Dordrecht, 1985) chapter 6.
\bibitem{HT}
        D.~Hartley and P.A.~Tuckey, {\em
        A Direct Characterisation of Gr\"obner Bases in Clifford and
        Grassmann Algebras,}
        Preprint MPI-Ph/93--96 (1993).
\bibitem{Stokes}
        T.~Stokes, {\em
        Gr\"obner bases in exterior algebra,}
        J.~Automated Reasoning {\bf 6}(1990)233--250.
\bibitem{EXCALC}
        E.~Schr\"ufer, {\em
        EXCALC, a system for doing calculations in the calculus of modern
        differential geometry, User's manual,}
        (The Rand Corporation, Santa Monica, 1986).

\end{thebibliography}

\end{document}