Séminaire du 11 janvier 2010,
14h00: Clément
Pernet, Université Joseph Fourier, Grenoble.
Calcul efficace de la forme normale de Hermite de
matrices entières.
En algèbre linéaire, les formes normales
triangulaires,
décrivent de nombreuses propriétés et invariants
d'une
matrice. La forme échelonnée réduite, ou forme de
Gauss-Jordan, dans un corps se généralise dans un anneau
en la
forme normale de Hermite. En théorie algorithmique des nombres,
c'est
une opération récurrente et couteuse, pour le calcul
avec des
formes modulaires ou la saturation d'idéaux par exemple. Nous
présenterons les éléments essentiels d'une
implémentation efficace du calcul de la forme normale de
Hermite de
matrices entières. Après avoir rappelé les
ingrédients de base pour le calcul en algèbre
linéaire
exacte dense, nous présenterons l'algorithme de Micciancio et
Warinschi, ainsi que plusieurs améliorations algorithmiques
rendant sa
mise en oeuvre particulièrement efficace.
Virginie Collette
Last modified: Mon Jan 4 17:25:58 CET 2010