Des méthodes symboliques-numériques et exactes pour la factorisation absolue des polynômes en deux variables
Institution:
NiceDisciplines:
Directors:
Abstract EN:
This thesis is about absolute factorization algorithms. The first chapter is a survey on this topic, and then we describe our contributions. They are divided in two parts. The first part corresponds to the symbolic-numeric study. We give a method which allows us to get an exact absolute factorization from an approximate one. Next, this method is used to get an absolute polynomial factorization algorithm. This algorithm uses ideas developped by A. Galligo, D. Rupprecht, and M. Van Hoeij. Thanks to the LLL algorithm, it allows us to get the absolute factorization for polynomials with big degree (bigger than 100). It was impossible before. In the second part, we give two algorithms. The first one adapt a "lifting and recombination'' scheme to the Gao's algorithm. We get then a new algorithm with a better complexity than the Gao's one. The second one is a Las Vegas algorithm. It is an absolute irreducibility test for polynomials with integer coefficients. This algorithm use modular computations, and the shape of the Newton's polytope.
Abstract FR:
Cette thèse porte sur les algorithmes de factorisation absolue. Elle débute par un état de l'art (avant notre travail) puis présente nos contributions. Celles-ci sont organisées en deux parties. La première partie correspond à l'étude symbolique-numérique. Nous donnons une méthode permettant d'obtenir une factorisation absolue exacte à partir d'une factorisation absolue approchée. Ensuite cette méthode est utilisée pour obtenir un algorithme de factorisation absolue. Cet algorithme reprend des idées développées par A. Galligo, D. Rupprecht, et, M. An Hoeij. Grâce à l'utilisation de l'algorithme LLL, notre algorithme permet d'obtenir la factorisation absolue de polynômes de grands degrés (supérieur à 100) jusqu'ici impossible. La deuxième partie présente deux algorithmes symboliques. Le premier est l'adaptation de la technique ``remonter-recombiner'' à l'algorithme de S. Gao. Nous obtenons ainsi un algorithme de factorisation absolue ayant une meilleure complexité que celui de S. Gao. Le deuxième est un algorithme, de type Las Vegas, qui nous permet de tester l'irréductibilité absolue d'un polynôme à coefficients entiers. L'approche proposée tire profit du calcul modulaire et de l'information contenu dans le polytope de Newton.