Séminaire du 05, by
Alin
Bostan, Projet Algorithmes.
Algorithmique rapide des sommes de Newton en petite
caractéristique
Dans cet exposé, nous considérerons le problème
algorithmique suivant : calculer les coefficients d'un
polynôme à partir des premières
sommes des puissances de ses racines. Nous
décrirons des algorithmes permettant d'effectuer
rapidement cette conversion pour des polynômes
à coefficients des nombres p-adiques. Nous
présenterons deux classes d'applications à
l'algorithmique sur des corps finis de petite
caractéristique : l'une concerne l'algèbre
linéaire parallèle à la Le Verrier,
l'autre le calcul de certains résultants
bivariés. Dans les deux cas, nos résultats
améliorent la complexité binaire des
algorithmes connus. Travail en collaboration avec
Laureano Gonzèlez-Vega, Hervé Perdry et
éric Schost.
Virginie Collette
Last modified: Thu May 12 15:49:23 CEST 2005