First presenter Co-presenter(s)
Name :  Adrien Poteaux * Name:   
E-mail: E-mail:  
Affiliation: University of Western Ontario Name:   
Department:   E-mail:    
City: Name:   
State/Province:   E-mail:    
Country: Canada Name:   
09-04  E-mail:    
Session: 9- Symbolic and Numeric Computation Schedule:
Saturday, 11:00
Related website:  
Title of
Computing Puiseux espansions : a new symbolic-numeric algorithm

Given a bivariate polynomial $F \in k[x,y]$ and $\alpha$ a root of the discriminant of $F$ in $y$, computing nunmerical approximations of Puiseux series of $F$ above $\alpha$ (i.e. the series in $(x-\alpha)$ solutions of the polynomial $F$ viewed as a univariate polynomial in $y$) is not an easy task. Usual algorithms, namely the Newton-Puiseux algorithm and its variants, are symbolic algorithms. Computing Puiseux series symbolically may be costly, because of the extension fields involved and the coefficients growth. Moreover, a numerical evaluation of these coefficients may sometimes need a high number of digits due to devastating cancellations. On the other hand, pure numerical computations cannot be used directly: the slightest approximation causes Newton-Puiseux algorithm to miss essential information, such as ramification indices. It also causes numerical instabilities, since any close approximation of $\alpha_0$ of $\alpha$ leads to expansions with a very small convergence radius $alpha-\alpha_0|$. To resolve the matter, we describe a new symbolic-numeric strategy. Indeed, studying the Newton-Puiseux algorithm, we can note that only two type of informations are needed exactly: Newton polygons and multiplicity structures of the characteristic polynomials. Thus, our strategy can be resume as follows: we first compute the Puiseux series modulo a well chosen prime number $p$. This give us the structure of the Puiseux series, namely the "polygon tree". Then, we show how to follow this polygon tree to compute numerical approximations of the Puiseux series coefficients.
This is a work made during my PhD at the University of Limoges, in collaboration with Marc Rybowicz.