@@ -1,101 +1,101 @@
-\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}
+\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}