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

\chapter{WU: Wu algorithm for poly systems}
\label{WU}
\typeout{{WU: Wu algorithm for polynomial systems}}

{\footnotesize
\begin{center}
Russell Bradford \\
School of Mathematical Sciences, University of Bath,\\
Bath, BA2 7AY, England \\[0.05in]
e--mail: rjb@maths.bath.ac.uk
\end{center}
}
\ttindex{WU}

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}\ttindex{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.