\chapter[COMPACT: Compacting expressions]{COMPACT: Package for compacting expressions} 
\label{COMPACT}
\typeout{{COMPACT: Package for compacting expressions}}

{\footnotesize
\begin{center}
Anthony C. Hearn\\
RAND\\
Santa Monica \\
CA 90407-2138, U.S.A. \\[0.05in]
e--mail: hearn@rand.org
\end{center}
}

\ttindex{COMPACT}\index{COMPACT package}\index{side relations}
\index{relations ! side} 
{COMPACT} is a package of functions for the reduction of a polynomial in
the presence of side relations.  The package defines one operator {COMPACT}
\index{COMPACT operator}
whose syntax is:

\begin{quote}
\k{COMPACT}(\s{expression}, \s{list}):\s{expression}
\end{quote}

\s{expression} can be any well-formed algebraic expression, and
\s{list} an expression whose value is a list
of either expressions or equations.  For example

\begin{verbatim}
    compact(x**2+y**3*x-5y,{x+y-z,x-y-z1});
    compact(sin(x)**10*cos(x)**3+sin(x)**8*cos(x)**5,
            {cos(x)**2+sin(x)**2=1});
    let y = {cos(x)**2+sin(x)**2-1};
    compact(sin(x)**10*cos(x)**3+sin(x)**8*cos(x)**5,y);
\end{verbatim}

{COMPACT} applies the relations to the expression so that an equivalent
expression results with as few terms as possible.  The method used is
briefly as follows:

\begin{enumerate}
\item Side relations are applied separately to numerator and denominator, so
that the problem is reduced to the reduction of a polynomial with respect to
a set of polynomial side relations.

\item Reduction is performed sequentially, so that the problem is reduced
further to the reduction of a polynomial with respect to a single
polynomial relation.

\item The polynomial being reduced is reordered so that the variables
(kernels) occurring in the side relation have least precedence.

\item Each coefficient of the remaining kernels (which now only contain
the kernels
in the side relation) is reduced with respect to that side relation.

\item A polynomial quotient/remainder calculation is performed on the
coefficient.  The remainder is
used instead of the original if it has fewer terms.

\item The remaining expression is reduced with respect to the side relation
using a ``nearest neighbour'' approach.
\end{enumerate}

