4
$\begingroup$

According to Wikipedia, a RUR of a zero-dimensional system consists in a linear combination of the variables, $x_0$ called ''separating variable'', and a system of equations : \begin{cases} h(x_0)=0\\ x_1=g_1(x_0)/g_0(x_0)\\ \quad\vdots\\ x_n=g_n(x_0)/g_0(x_0), \end{cases} where $h$ is a univariate polynomial in $x_0$ of degree $D$ and $g_0, \dots, g_n$ are univariate polynomials in $x_0$ of degree less than $D$.

Is there a way to find such a system in Mathematica, given a list of polynomials?

$\endgroup$
3
$\begingroup$

I do not recall offhand how these are computed in general. For the case of distinct roots I can illustrate one method. I'll take the example in that Wikipedia article.

We have polynomials as below.

polys = {x^2-1, (x-1)*(y-1), y^2-1};

We take as separating element t = (x-y)/2.

seppoly = t-(x-y)/2;

First compute the polynomial referred to as h(t). Then take its derivative.

tpoly = 
 First[GroebnerBasis[Join[polys, {seppoly}], t, {x, y}, 
   MonomialOrder -> EliminationOrder]]
dtpoly = D[tpoly, t];

(* Out[132]= -t + t^3 *)

Now call that derivative den and find "numerator" polynomials g1 and g2 such that den*x=g1 and similar for y. I use GroebnerBasis with a monomial order that is efficient for eliminating {x,y,den} and in effect solving for {g1,g2} in terms of t.

gb = GroebnerBasis[
  Join[polys, {seppoly, dtpoly - den}, den*{x, y} - {g1, g2}], {g1, 
   g2, t}, {x, y, den}, 
  MonomialOrder -> {{1, 1, 1, 0, 0, 0}, {0, 0, -1, 0, 0, 0}, {0, -1, 
     0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 
     0, -1, 0}}]

(* Out[161]= {-t + t^3, 1 + g2 + 2 t - t^2, 1 + g1 - 2 t - t^2} *)

The numerators are readily recovered.

numerators = {g1, g2} /. 
  First[Solve[Rest[gb] == 0, {g1, g2}]]

(* Out[164]= {-1 + 2 t + t^2, -1 - 2 t + t^2} *)

The rational univariate representation:

rur = Join[{tpoly}, {x, y} - numerators/dtpoly]

(* Out[167]= {-t + t^3, -((-1 + 2 t + t^2)/(-1 + 3 t^2)) + 
  x, -((-1 - 2 t + t^2)/(-1 + 3 t^2)) + y} *)
| improve this answer | |
$\endgroup$
  • $\begingroup$ Is there a general way to find a separating element? Or does one just have to try different things? $\endgroup$ – Thomas Ahle Mar 23 at 13:26
  • 2
    $\begingroup$ A random linear combination of the variables will be a separating element with probability 1. $\endgroup$ – Daniel Lichtblau Mar 23 at 13:30
  • $\begingroup$ Could you talk about how you came up with the matrix you used in MonomialOrder? $\endgroup$ – J. M.'s discontentment Mar 25 at 1:19
  • $\begingroup$ @J.M'sTech... (First, thanks for fixing the typo) It is basically a block order with the elimination variables handled in a degree-reverse-lax block. The lower block is constructed to soleve for two variables in terms of a third, and those two are weighted equally for efficiency. Provided we have a correct separating element this will work since both will end up as linear leading monomials. I could have used something closer to the matrix form of EliminationOrder and maybe that would in general be more efficient for the purposes at hand. $\endgroup$ – Daniel Lichtblau Mar 25 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.