Artifact 563835c1f90111544c7a8aab88b356a7ab3563df3625b882f3b27e577eb4b869:

• File r34/doc/compact.tex — part of check-in [f2fda60abd] at 2011-09-02 18:13:33 on branch master — Some historical releases purely for archival purposes

  git-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/trunk/historical@1375 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: arthurcnorman@users.sourceforge.net, size: 4204) [annotate] [blame] [check-ins using] [more...]

\documentstyle {article}
%\textwidth 15.5cm\textheight 22.0cm\columnwidth\textwidth
%\hoffset-1.5cm\voffset-1.5cm
\begin{document}
%\parskip 10pt plus 1pt \parindent 0pt
\title{{COMPACT} User's Manual}
\author{Anthony C. Hearn\\
RAND\\
Santa Monica CA 90407-2138\\[0.05in]
Email: hearn@rand.org}
\date{15 April 1989}
\maketitle
{COMPACT} is a package of functions for the reduction of a polynomial in
the presence of side relations.  The package defines one operator {COMPACT}
whose syntax is:
\begin{verbatim}
    COMPACT(<expression>,<list>):<expression>.
\end{verbatim}
{\tt <expression>} can be any well-formed algebraic expression, and
{\tt <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 neighbor" approach.
\end{enumerate}

As with the traveling salesman problem, a nearest neighbor approach to
reduction does not necessarily achieve an optimal result.  In most cases
it will be within a factor of two from the optimal result, but in extreme
cases it may be much further away.

Another source of sub-optimal results is that the given expression
is reduced sequentially with respect to the side relations.  So for
example in the case
\begin{verbatim}
        compact((a+b+c)*(a-b-c)*(-a+b-c)*(-a-b+c),
                {x1=a+b+c,x2=a-b-c,x3=-a+b-c,x4=-a-b+c})
\end{verbatim}
the expression is actually $x_{1}x_{2}x_{3}x_{4}$, but any given relation
cannot reduce the size of the expanded form
$a^{4}-2a^{2}b^{2}-2a^{2}c^{2}+b^{4}-2b^{2}c^{2}+c^{4}$
of the original expression, and so the final result is far from optimal.

The only other program we have heard about that considers the compaction
problem is that of Hornfeldt (L. Hornfeldt, ``A Sum-Substitutor used as
Trigonometric Simplifier", Proc. EUROCAM '82, 188-195, published as
Lecture Notes on Comp. Science, No. 144, Springer-Verlag, Berlin, 1982).
However, Hornfeldt reorders expressions so that the kernels in a side
relation have highest order.  Consequently, their coefficients are
polynomials rather than integers or other constants as in our approach.
Furthermore, it is not clear just how general Hornfeldt's approach is from
his description, since he only talks about sine and cosine substitutions.

There are a number of projects that this work immediately suggests.  For
example:
\begin{enumerate}
\item How does one do the reduction with the side relations in parallel?
The above example shows this is necessary for an optimal solution.

\item Should one reduce the side relations to a Groebner or other basis
before doing any reduction?

\item Should one check for the consistency of the basis?

\item How does one do factorization and gcds on a polynomial whose
variables are related by a set of side relations?
\end{enumerate}

The author would be interested in hearing from anyone wishing to work with
him on any of these problems.
\end{document}