20.62 WU: Wu Algorithm for Polynomial Systems

This is a simple implementation of the Wu algorithm implemented in REDUCE working directly from [Wt87].

Author: Russell Bradford.

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:

 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});

calls wu with the named polynomials, and with the variable ordering \({\tt x} > {\tt y} > {\tt z}\). In this example, r is a parameter.

The result is

    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},

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

       2
    + z  - 1,

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

          2
   x*y + z  - 1},

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

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

on trwu;

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.

Hosted by