Computing Puiseux series: a fast divide and conquer algorithm (Q2077183)

The study of Puiseux expansions of bivariate polynomials and local parametrizations of the associated algebraic curve are of great importance in Algebraic Geometry. Basically all relevant information on singularities and the local behavior of an algebraic curve is contained in the corresponding Puiseux expansions or local parametrizations, which are given by its so-called singular part. A rational version of the computation has turned out to be particularly useful and computationally fast. In this paper, the authors improve the bound on the number of terms in the singular part. The rational version of the algorithm for computing Puiseux expansions, a divide and conquer strategy for factorizations and dynamic evaluation are used. These underlying algorithms, their worst-case complexity and several applications are studied. In particular, a fast analytic factorization of the given polynomial and the computation of the genus are shown with exact or probabilistic methods. The paper can be seen as a main reference work on the computation of Puiseux expansions and local parametrizations of algebraic curves where the coefficient field has zero or positive characteristic. The applications are manifold and not limited to Algebraic Geometry.