04.07.2012

14:00

SP2 416

Adrien Poteaux (Université Lille)

SC: Towards a fast Newton-Puiseux algorithm?

We will present a work in progress about the arithmetic complexity of the Newton-Puiseux algorithm. Puiseux series are fundamental objects of the theory of algebraic curves. Last and best (to our knowledge) result [1] about the arithmetic complexity for computing the Puiseux series of a polynomial F 2 L[X; Y ] is in O~(D5) where D is the total degree of F. This improvement from [2] (who gives a result in O(D8)) is mainly due to two points:  we truncate the powers of X,  we show how to use fast multiplication during the algorithm. However, with such a complexity, this algorithm cannot be considered as a fast one. We will present some ideas that will hopefully lead us to a O~(D3) complexity. The main ones are:  We factorize the input polynomials during the algorithm, so that we make substitutions only in the part of the polynomial we are interested in,  We shift the penultimate coecient to compute common terms at once, which enable to control the number of recursive call of the Newton-Puiseux algorithm me make.  We use relax algorithms (see Jeremy Berthomieux's talk) so that we can truncate the power of X without a priori bound. In particular, we will provide a relax algorithm to apply the Hensel lemma,  We rene our truncation bounds to improve the complexity result. This work is a collaboration with Marc Rybowicz (university of Limoges). References [1] Adrien Poteaux and Marc Rybowicz. Complexity bounds for the rational newton-puiseux algorithm over nite elds. Applicable Algebra in Engineering, Communication and Computing, 22:187-217, 2011. 10.1007/s00200-011-0144-6. [2] Dominique Duval. Rational Puiseux Expansions. Compositio Mathematica, 70:119-154, 1989.

Back to Events page