reduce-historical/r35/lib/wu.tex

\documentstyle[fullpage]{article}

\pagestyle{empty}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}
\title{An Implementation of the Wu Algorithm}
\author{Russell Bradford \\
School of Mathematical Sciences,\\
University of Bath,\\
Claverton Down,\\
Bath, BA2 7AY \\
\tt rjb@maths.bath.ac.uk}
\date{}
\maketitle\thispagestyle{empty}

This is a simple implementation of the Wu algorithm implemented in Reduce
3.3, working directly from
``A Zero Structure Theorem for Polynomial-Equations-Solving,''
Wu Wen-tsun, Institute of Systems Science, Academia Sinica, Beijing.

Its purpose was to aid my understanding of the algorithm, so the code is
simple, and has a lot of tracing included. This is a working implementation,
but there is magnificent scope for improvement and optimisation. Things
like using intelligent sorts on polynomial lists, and avoiding the
re-computation of various data spring easily to mind. Also, an attempt
at factorization of the input polynomials at each pass might have beneficial
results. Of course, exploitation of the natural parallel structure is a must!

All bug fixes and improvements are welcomed.

The interface:
\begin{verbatim}
wu( {x^2+y^2+z^2-r^2, x*y+z^2-1, x*y*z-x^2-y^2-z+1}, {x,y,z});
\end{verbatim}
calls {\tt wu} with the named polynomials, and with the variable ordering
${\tt x} > {\tt y} > {\tt z}$. In this example, {\tt r} is a parameter.

The result is
\begin{verbatim}
    2    3    2
{{{r  + z  - z  - 1,

    2  2    2      2    4    2  2    2
   r *y  + r *z + r  - y  - y *z  + z  - z - 2,

          2
   x*y + z  - 1},

  y},

    6  4      6  2    6      4  7      4  6      4  5      4  4
 {{r *z  - 2*r *z  + r  + 3*r *z  - 3*r *z  - 6*r *z  + 3*r *z  + 3*

    4  3      4  2      4      2  10      2  9      2  8      2  7
   r *z  + 3*r *z  - 3*r  + 3*r *z   - 6*r *z  - 3*r *z  + 6*r *z  +

       2  6      2  5      2  4      2  3      2    13      12    11
    3*r *z  + 6*r *z  - 6*r *z  - 6*r *z  + 3*r  + z   - 3*z   + z

         10    9      8      7    6      4      3    2
    + 2*z   + z  + 2*z  - 6*z  - z  + 2*z  + 3*z  - z  - 1,

    2   2    3    2
   y *(r  + z  - z  - 1),

          2
   x*y + z  - 1},

      2    3    2
  y*(r  + z  - z  - 1)}}
\end{verbatim}
namely, a list of pairs of characteristic sets and initials for the
characteristic sets.

Thus, the first pair above has the characteristic set
$$ r^2 + z^3 - z^2 - 1,
r^2 y^2 + r^2 z + r^2 - y^4 - y^2 z^2 + z^2 - z - 2,
x y + z^2 - 1$$
and initial $y$.

According to Wu's theorem, the set of roots of the original polynomials
is the union of the sets of roots of the characteristic sets,
with the additional constraints that the
corresponding initial is non-zero. Thus, for the first pair above, we find the
roots of $\{ r^2 + z^3 - z^2 - 1, \ldots~\}$ under the constraint that
$y \neq 0$. These roots, together with the roots of the other
characteristic set (under the constraint of $y(r^2+z^3-z^2-1) \neq 0$),
comprise all the roots of the original set.

Additional information about the working of the algorithm can be gained by
\begin{verbatim}
on trwu;
\end{verbatim}
This prints out details of the choice of basic sets, and the computation
of characteristic sets.

The second argument (the list of variables) may be omitted, when all the
variables in the input polynomials are implied with some random ordering.
\end{document}