Bivariate Triangular Decompositions in the Presence of Asymptotes

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Given two coprime polynomials $P$ and $Q$ in $\mathbb{Z}[x,y]$ of degree at most $d$ and coefficients of bitsize at most $\tau$, we address the problem of computing a triangular decomposition $\{(U_i(x),V_i(x,y))\}_{i\in\cal I}$ of the system $\{P,Q\}$. The state-of-the-art worst-case bit complexity for computing such triangular decompositions when the curves defined by the input polynomials do not have common vertical asymptotes is in $\tilde{O}_B(d^6+d^5\tau)$ [Bouzidi et al. 2015, Prop. 16], where $\tilde{O}$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity. We show that the same worst-case bit complexity can be achieved even when the curves defined by the input polynomials may have common vertical asymptotes. We actually present a refined bit complexity in $\tilde{O}_B(d_x^3d_y^3 + (d_x^2d_y^3+d_xd_y^4)\tau)$ where $d_x$ and $d_y$ bound the degrees of $P$ and $Q$ in $x$ and $y$, respectively. We also prove that the total bitsize of the decomposition is in $\tilde{O}((d_x^2d_y^3+d_xd_y^4)\tau)$.
Type de document :
Rapport
[Research Report] INRIA. 2015
Domaine :

Littérature citée [9 références]

https://hal.inria.fr/hal-01200802
Contributeur : Sylvain Lazard <>
Soumis le : jeudi 17 septembre 2015 - 11:33:00
Dernière modification le : mardi 13 décembre 2016 - 15:45:55
Document(s) archivé(s) le : mardi 29 décembre 2015 - 07:42:52

Fichier

Bivariate-triang-decomp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : hal-01200802, version 1

Citation

Sylvain Lazard, Marc Pouget, Fabrice Rouillier. Bivariate Triangular Decompositions in the Presence of Asymptotes. [Research Report] INRIA. 2015. 〈hal-01200802〉

Consultations de
la notice

456

Téléchargements du document