Rational Univariate Representations of Bivariate Systems and Applications

Yacine Bouzidi 1 Sylvain Lazard 1 Marc Pouget 1 Fabrice Rouillier 2
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00802698
Contributor : Marc Pouget <>
Submitted on : Monday, November 25, 2013 - 9:40:11 AM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Long-term archiving on : Wednesday, February 26, 2014 - 4:23:47 AM

Files

RR-8262.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00802698, version 2
  • ARXIV : 1303.5042

Citation

Yacine Bouzidi, Sylvain Lazard, Marc Pouget, Fabrice Rouillier. Rational Univariate Representations of Bivariate Systems and Applications. [Research Report] RR-8262, INRIA. 2013, pp.26. ⟨hal-00802698v2⟩

Share

Metrics

Record views

531

Files downloads

277