Séminaires : Structures algébriques ordonnées

Equipe(s) : lm,
Responsables :F. Delon, M. Dickmann, D. Gondard
Email des responsables : dickmann@math.univ-paris-diderot.fr
Salle : 1013
Adresse :Sophie Germain

Mardi de 14h00 à 15h45
Page du séminaire et programme
Abonnement à la liste de diffusion

Orateur(s) Marie Françoise Roy - Rennes I,
Titre Complexité du calcul de la topologie d'une courbe algébrique réelle
Horaire14:00 à 15:45
Diffusion Code YFu1bz
RésumeWe give a deterministic algorithm to compute the topology of a real algebraic curve defined by an integer bivariate polynomial of degree bounded by d and bitsize bounded by τ. . Our analysis yields the upper bound Õ(d^5 τ + d^6 ) on the bit complexity of our algorithm. Compared to existing algorithms with similar complexity, our method does not consider any change of coordinates, and gives cylindrical algebraic decomposition of the curve. We use two main ingredients: First, we derive amortized quantitative bounds on the the roots of polynomials with algebraic coefficients as well as adaptive methods for computing the roots of such polynomials that actually exploit this amortization. Our second ingredient is a novel approach for the computation of the local topology of the curve in a neighbourhood of all critical points. Joint work with Daouda Niang Diatta · Sény Diatta ·Fabrice Rouillier · Michael Sagraloff
AdresseZoom ID 858 4156 0806