| Orateur(s) | Marie Françoise Roy - Rennes I,
|
| Titre | Complexité du calcul de la topologie d'une courbe algébrique réelle |
| Date | 16/02/2021 |
| Horaire | 14:00 à 15:45 |
|
| Diffusion | Code YFu1bz |
| Résume | We 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 |
| Salle | https://us02web.zoom.us/j/85841560806?pwd=SG5KSEUwNlUvNnJFWHBiaHhUNGt5UT09 |
| Adresse | Zoom ID 858 4156 0806
|
