Rational Univariate Representations of Bivariate Systems and Applications

We address the problem of solving systems of two bivariate polynomials of total degree at most $d$ with integer coefficients of maximum bitsize $\tau$. It is known that a linear separating form, that is a linear combination of the variables that takes different values at distinct solutions of the system, can be computed in $\sOB(d^{8}+d^7\tau)$ bit operations (where $O_B$ refers to bit complexities and $\sO$ to complexities where polylogarithmic factors are omitted) and we focus here on the computation of a Rational Univariate Representation (RUR) given a linear separating form. We present an algorithm for computing a RUR with worst-case bit complexity in $\sOB(d^7+d^6\tau)$ and bound the bitsize of its coefficients by $\sO(d^2+d\tau)$. We show in addition that isolating boxes of the solutions of the system can be computed from the RUR with $\sOB(d^{8}+d^7\tau)$ bit operations. Finally, we show how a RUR can be used to evaluate the sign of a bivariate polynomial (of degree at most $d$ and bitsize at most $\tau$) at one real solution of the system in $\sOB(d^{8}+d^7\tau)$ bit operations and at all the $\Theta(d^2)$ {real} solutions in only $O(d)$ times that for one solution.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00802698
Author Bouzidi, Yacine, Lazard, Sylvain, Pouget, Marc, Rouillier, Fabrice
Maintainer CCSD
Last Updated May 8, 2026, 03:03 (UTC)
Created May 8, 2026, 03:03 (UTC)
Identifier Report N°: RR-8262
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Effective Geometric Algorithms for Surfaces and Visibility (VEGAS) ; Centre Inria de l'Université de Lorraine ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO) ; Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
creator Bouzidi, Yacine
date 2013-03-20T00:00:00
harvest_object_id ce2f7561-c399-40cc-ab58-4b43982d94f7
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-11-04T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1303.5042
set_spec type:REPORT