What is a RUR ?

When a system $\mathcal{S}$ depends on several variables $X_1, \dots, X_n$, but has a finite number of complex roots, which can be detected at an intermediate step in the computations, one can simplify the study by computing a, so called, Rational Univariate Representation (RUR) of the roots, that consists of a linear form $t = \sum_{i = 0}^n a_i X_i$ that is injective on the set of complex roots and $n + 1$ univariate polynomials $f_t (T), f_1 (T), \ldots, f_n (T)$ depending on a new independent variable and with coefficients in the same ground field as the system.

If $V(\mathcal{S}) \subset \mathbb{C}^n$ is the set of complex roots of $\mathcal{S}$ and $V (f_t) \subset \mathbb{C}$ the set of complex roots of $f_t$, the RUR associated to $t$ defines a bijection between $V (\mathcal{S})$ and $V (f_t)$ that preserves the real roots and the multiplicities :

\[\begin{array}{ccc} V (\mathcal{S}) & \longrightarrow & V (f_t)\\ \alpha = (\alpha_1, \ldots, \alpha_n) & \rightarrow & t (\alpha) = \sum_{i = 1}^n a_i \alpha_i\\ \left( \frac{f_1 (\beta)}{f_t^{'} (\beta)}, \ldots, \frac{f_n (\beta)}{f_t^{'} (\beta)} \right) & \leftarrow & \beta \end{array}\]

Installation

using Pkg
Pkg.add(url="https://gitlab.inria.fr/NewRUR/RationalUnivariateRepresentation.jl");

Example

We compute a parametrization of roots of a zero-dimensional system sys using the function zdim_parameterization:

using Nemo, RationalUnivariateRepresentation

R, (x0, x1, x2) = QQ["x0","x1","x2"]
sys = [x0^2 + 2*x1^2 + 2*x2^2 - x0, 2*x0*x1 + 2*x1*x2 - x1, x0 + 2*x1 + 2*x2 - 1]

param = zdim_parameterization(sys) #  compute parametrization

The output param would be something like the following:

4-element Vector{Vector{Rational{BigInt}}}:
 [0, 1//84, 1//84, -10//21, 1]     # Coefficients of f(T)
 [1//84, 1//21, -20//21, 46//21]   # Coefficients of f1(T)
 [0, 1//42, -3//14, 3//7]          # Coefficients of f2(T)
 [0, 1//84, 1//42, -10//7, 4]      # Coefficients of f3(T)

About the implementation

The main function, RationaUnivariateRepresentation.zdim_parametrization, computes a parametrization of the roots of a given system of equations with coefficients in $\mathbb{Q}$ or $\frac{\mathbb{Z}}{p\mathbb{Z}}$. Precisely, it computes a RUR of the radical of the ideal generated by the equations. When combined with some root isolator like in PACE.jl, such a RUR allows to get isolating boxes for the real solutions of the system.

The implementation uses the algorithm from [1] and it intensively uses the Julia package Groebner.jl described in [2].

References

[1] Alexander Demin, Fabrice Rouillier and Joao Ruiz, Reading Rational Univariate Representations on lexicographic Groebner bases,arXiv:2402.07141

[2] Alexander Demin, Shashi Gowda, Groebner.jl: A package for Gröbner bases computations in Julia, arXiv:2304.06935