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.
|