Function Repository Resource:

RationalUnivariateRepresentation

Get a rational univariate representation for a general polynomial system

Contributed by: Daniel Lichtblau

ResourceFunction["RationalUnivariateRepresentation"][polys,vars,t]

gives a rational univariate representation in terms of a new variable t for the polynomial system polys in variables vars.

Details and Options

The rational univariate representation (RUR) is effectively a triangular representation of the solution set of a system of multivariate polynomials. It preserves multiplicities of the solutions to the original system.

The system polys must be zero dimensional, that is, have only finitely many solutions in the given vars.

The new variable is often referred to as a separating variable.

An RUR has a single polynomial p(t) for the separating variable t. There is a linear polynomial in each of the respective vars with another term that is a rational function in t. The denominator in all cases is the derivative polynomial p'(t), and all numerators have degree less than that of this denominator. Thus all solutions for vars are effectively presented as rational functions in t. We obtain numeric values by evaluating at each of the roots of p(t).

An RUR is similar to a Groebner basis in lexicographic term order, in that both give a triangular form for the solution set of a given set of polynomials. When the Shape Lemma applies with respect to the lowest ordered variable, the Groebner basis gives a univariate representation for the remaining variables.

RationalUnivariateRepresentation uses a probabilistic method to find a separating element and may fail, in which case it will return unevaluated.

Examples

Basic Examples (2)

Compute a rational univariate representation for the polynomial system (x²-1,(x-1)*(y-1),y²-1):

In[1]:=

$polys = {x^2 - 1, (x - 1)*(y - 1), y^2 - 1}; rur = ResourceFunction["RationalUnivariateRepresentation"][ polys, {x, y}, t]$

Out[2]=

Solve for t:

In[3]:=

Out[3]=

Get linear polynomials in (x,y):

In[4]:=

Out[4]=

Solve these:

In[5]:=

Out[5]=

Compare to solving the original system:

In[6]:=

Out[6]=

Compute a rational univariate representation for a pair of cubic polynomials:

In[7]:=

$polys = {x^3 \[Minus] 3 x^2 + 3 x*y \[Minus] y^2 + 2 y \[Minus] 2, 2 x^2 + 5*y^3 + y - 3}; ResourceFunction["RationalUnivariateRepresentation"][polys, {x, y}, t]$

Out[8]=

Scope (2)

RationalUnivariateRepresentation can find approximate results when input precision is finite:

In[9]:=

$polys = {x^3 \[Minus] 3 x^2 + 3 x*y \[Minus] y^2 + 2 y \[Minus] 2, 2 x^2 + 5*y^3 + y - 3}; ResourceFunction["RationalUnivariateRepresentation"][ N[polys, 40], {x, y}, t]$

Out[10]=

A rational univariate representation can be computed for polynomials that have parametrized coefficients:

In[11]:=

$polys = {x^3 \[Minus] x^2 + x*y \[Minus] y^2 + 2 y \[Minus] a, 2 x^2 + y^3 + y - b}; ResourceFunction["RationalUnivariateRepresentation"][polys, {x, y}, t]$

Out[12]=

Options (1)

Compute an RUR using a prime modulus:

In[13]:=

$polys = {-6*p^3 + 4*p^3*phi^3 + 15*phi^3*s^3*p - 3*phi^3*s^5 - 12*phi^3*s*p^2 - 3*phi^3*s*p + phi^3*s^3, -9*phi^3*s^2*p - 5*phi^3*s^2 - 6*s*p^3 + 3*phi^3*s^4 + 5*phi^3*p, -12*s^2*p - 6*s^2 + 3*s^4 + 4*phi^2 + 3 + 12*p}; ResourceFunction[ "RationalUnivariateRepresentation"][polys, {s, p, phi}, t, Modulus -> 29]$

Out[14]=

Possible Issues (3)

RationalUnivariateRepresentation will be unable to compute a result in finite precision unless it is sufficient to do the needed internal computations:

In[15]:=

$polys = {x^3 \[Minus] 3 x^2 + 3 x*y \[Minus] y^2 + 2 y \[Minus] 2, 2 x^2 + 5*y^3 + y - 3}; ResourceFunction["RationalUnivariateRepresentation"][ N[polys, 20], {x, y}, t]$

Out[16]=

It can be quite slow to compute an RUR for systems when coefficients involve radicals or otherwise become large during the computation:

In[17]:=

$polys = {x0^2 + x1^2 + x2^2 - 1, x0*x3 + x1*x4 + x2*x5, x3^2 + x4^2 + x5^2 - 3/10, x3^2 + x4^2 - 2*x2*x4 + x2^2 + x5^2 + 2*x1*x5 + x1^2 - 1/4, x3^2 + Sqrt[3]*x2*x3 + 3/4*x2^2 + x4^2 - x2*x4 + 1/4*x2^2 + x5^2 - Sqrt[3]*x0*x5 + x1*x5 + 3/4*x0^2 - Sqrt[3]/2*x0*x1 + 1/4*x1^2 - 1/4, x3^2 - 2/3*Sqrt[6]*x1*x3 + Sqrt[3]/3*x2*x3 + 2/3*x1^2 - Sqrt[18]/9*x1*x2 + 1/12*x2^2 + x4^2 + 2/3*Sqrt[6]*x0*x4 - x2*x4 + 2/3*x0^2 - Sqrt[6]/3*x0*x2 + 1/4*x2^2 + x5^2 - Sqrt[3]/3*x0*x5 + x1*x5 + 1/12*x0^2 - Sqrt[3]/6*x0*x1 + 1/4*x1^2 - 1/4}; TimeConstrained[ rur = ResourceFunction["RationalUnivariateRepresentation"][ polys, {x0, x1, x2, x3, x4, x5}, t];, 60]$

Out[18]=

We can compute this much faster if we use approximate coefficients to sufficient precision:

In[19]:=

Out[19]=

The result has polynomials in the separating variable of degree as large as 23:

In[20]:=

Out[20]=

If a polynomial system does not satisfy the Shape Lemma then RationalUnivariateRepresentation may either fail to find an RUR or lose multiplicity in the process:

In[21]:=

$polysCaprasse = {-2*x + 2*t*x*y - z + y^2*z, 2 + 4*x^2 - 10*t*y + 4*t*x^2*y - 10*y^2 + 2*t*y^3 + 4*x*z - x^3*z + 4*x*y^2*z, -x + t^2*x - 2*z + 2*t*y*z, 2 - 10*t^2 - 10*t*y + 2*t^3*y + 4*x*z + 4*t^2*x*z + 4*z^2 + 4*t*y*z^2 - x*z^3}; First@Timing[ rur = ResourceFunction["RationalUnivariateRepresentation"][ polysCaprasse, {x, y, z, t}, s]]$

Out[22]=

Use the RUR obtained to get solutions to the original system:

In[23]:=

ssols = NSolve[rur[[1]] == 0, s];
linpolys = Rest[rur] /. ssols;
allsols = Map[First[NSolveValues[#, {t, x, y, z}]] &, linpolys];
Length[allsols]

Out[26]=

Compare to the result from NSolve to see that some of the multiplicity has been lost:

In[27]:=

Out[27]=

Also check with the resource function CountPolynomialSolutions:

In[28]:=

Out[28]=

The number of distinct roots is 32:

In[29]:=

Out[29]=

A small perturbation of the second polynomial will cause the system to have 56 distinct roots; this can be assessed from the degree of the separating variable polynomial:

In[30]:=

$rur = ResourceFunction["RationalUnivariateRepresentation"][ polysCaprasse + {0, 1`600/10^20, 0, 0}, {x, y, z, t}, s]; Exponent[rur[[1]], s]$

Out[31]=

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

1.0.0 – 14 June 2024

Source Metadata

Citation:
- Fabrice Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. Applicable Algebra in Engineering, Communication and Computing 9:433-461, 1999. DOI: 10.1007/s002000050114
- Eberhard Becker, Teo Mora, Maria Grazia Marinari and Carlo Traverso. The shape of the Shape Lemma.
  Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation (ISSAC '94) 129-133, ACM, 1994. DOI: 10.1145/190347.190382

Related Resources

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License