RS.jl

RS.jl offers a Julia interface to some functions of the RS C-library used in Maple software for the study of real roots of systems of polynomial equations and inequations, namely the real root isolation of univariate polynomials and zero-dimensional (with a finite number of complex solutions) systems with rational coefficients.

Univariate Isolation

The roots of $P (X) =\sum_{i = 0}^n a_i X, a_i \in \mathbb{Q}$, can be exactly represented by:

an isolating interval $\left] \frac{n_l}{d_l}, \frac{n_r}{d_r} \right[$ containing a unique real solution of $P (X) = 0$ with the convention that $\left] \frac{b}{c}, \frac{b }{c} \right[$ is exactly the rational number $\frac{b}{c}$,
$\overline{P}$, the square-free part of $P$, that is ${\overline{P}}=\frac{P}{gcd(P, P')}$.

Such a representation allows, for example, to provide a numerical approximation of the roots with an arbitrary precision set by the user, $\overline{P}$ taking opposite signs at the left and at the right of any isolating interval. Using simple algorithms one can also compare, add, multiply roots.

See RS.rs_isolate

Multivariate Isolation

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 with rational coefficients $t = \sum_{i = 0}^n a_i X_i$ that is injective on the set of complex roots and $n + 1$ univariate polynomials with rational coefficients in a new independent variable: $f_t (T), f_1 (T), \ldots, f_n (T)$. 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)}{\overline{f_t}^{'} (\beta)}, \ldots, \frac{f_n (\beta)}{\overline{f_t}^{'} (\beta)} \right) & \leftarrow & \beta \end{array}\]

If the real roots of $f_t$ have been isolated by means of intervals with rational bounds $\left\{ \left] \frac{n_{i, l}}{d_{i, l}}, \frac{n_{i, r}}{d_{i, r}} \right[, i = 1 \ldots l \right\}$, one can then use multi-precision interval arithmetic in order to compute boxes $\frac{f_1 \left( \left] \frac{n_{i, l}}{d_{i, l}}, \frac{n_{i, r}}{d_{i, r}} \right[ \right)}{\overline{f_t}^{'} \left( \left] \frac{n_{i, l}}{d_{i, l}}, \frac{n_{i, r}}{d_{i, r}} \right[ \right)} \times \ldots \times \frac{f_n \left( \left] \frac{n_{i, l}}{d_{i, l}}, \frac{n_{i, r}}{d_{i, r}} \right[ \right)}{\overline{f_t}^{'} \left( \left] \frac{n_{i, l}}{d_{i, l}}, \frac{n_{i, r}}{d_{i, r}} \right[ \right)}$ with rational bounds that isolate the real roots of $V (\mathcal{S})$ and that can be refined up to an arbitrary precision fixed by the user.

See

Given a root represented by an isolating interval, a common method for refining it—whether to achieve higher precision or to ensure certain properties, such as sign invariance when evaluating another nonzero polynomial at the root—involves applying the interval Newton's method. This iterative approach refines the initial interval by computing Newton steps in an interval form and intersecting the result with the previous interval at each iteration. This process progressively narrows the isolating interval, improving the accuracy of the root representation.

See RS.rs_newton

Plot implicit plane algebraic curves

See RS.rs_tci_points

References

[1] Efficient isolation of polynomial's real roots. Fabrice Rouillier, Paul Zimmermann. Journal of Computational and Applied Mathematics, 2004, 162 (1), pp.33-50. ⟨10.1016/j.cam.2003.08.015⟩
[2] Solving Zero-Dimensional Systems through the Rational Univariate Representation, Fabrice Rouillier, Applicable Algebra in Engineering, Communication and Computing, 1999, 9 (5), pp.433-461. ⟨10.1007/s002000050114⟩