Amortized complexity bounds for polynomials with algebraic coefficients and application to curve topology

Speakers: Daouda Diatta\n\nLet $P \in \mathbb{Z} [X, Y]$ be a square-free polynomial of total degree $d$ and coefficients of bitsize\n $\tau$, and $\mathcal{C}(P) := \{ (x,y) \in \mathbb{R}^2, P (x,y)= 0 \}$ be the real algebraic curve defined by $P$. \nWe describe an algorithm performing no change of variable and computing the topology of $\mathcal{C} (P)$ $i.e$ a\n straight-line planar graph isotopic to $\mathcal{C} (P)$ inside $\mathbb{R}^2$ in $\tilde{O} (d^5 \tau\n + d^6)$ bit operations. Compared to state of the art algorithms used for computing a Cylindrical Algebraic Decomposition, this result avoids entirely a generic shear. \nOur result is based on two main ingredients:First, we derive amortized quantitative bounds on the roots of polynomials with algebraic coefficients as well as adaptive methods for computing the roots of bivariate polynomial systems that actually exploit this amortization. Our second ingredient is a novel approach for the computation of the local topology of the curve in a neighborhood of all singular points.\n\nhttps://indico.math.cnrs.fr/event/16690/