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$. We suppose known a linear separating form (that is a linear combination of the variables that takes different values at distinct solutions of the system) and focus on the computation of a Rational Univariate Representation (RUR). 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)$ (where $O_B$ refers to bit complexities and $\sO$ to complexities where polylogarithmic factors are omitted). 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)$ solutions in only $O(d)$ times that for one solution.
Type de document :
Communication dans un congrès
ISSAC - 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. pp.109-116, 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00809430
Contributeur : Sylvain Lazard <>
Soumis le : mardi 9 avril 2013 - 11:56:51
Dernière modification le : mardi 13 décembre 2016 - 15:42:09
Document(s) archivé(s) le : lundi 3 avril 2017 - 02:29:28

Fichier

Issac13_rur_complexity.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00809430, version 1

Collections

Citation

Yacine Bouzidi, Sylvain Lazard, Marc Pouget, Fabrice Rouillier. Rational Univariate Representations of Bivariate Systems and Applications. ISSAC - 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. pp.109-116, 2013. <hal-00809430>

Partager

Métriques

Consultations de
la notice

334

Téléchargements du document

180