Résumé de l'exposé :

Nous traiterons dans cet exposé d'un des problèmes classiques en
algèbre linéaire: le calcul du polynôme caractéristique et plus
généralement, celui de la forme normale de Frobenius d'une matrice.
Nous nous intéresserons plus particulièrement aux matrices denses à
coefficients dans des corps finis.

Dans une première partie, nous introduirons nos résultats concernant
la triangularisation de matrices denses. Une nouvelle approche
utilisant les puissantes routines numériques des BLAS pour le calcul
exact a permis d'atteindre des performances jusque là inégalées.
Ces routines efficaces en pratique serviront de brique de base pour
les algorithmes de calcul du polynôme caractéristique.

Dans une deuxième partie, nous présenterons deux algorithmes pour le
calcul du polynôme caractéristique, basés sur des triangularisation
par blocs. Le premier est inspiré des méthodes de Danilevski et de
Krylov. Nous en présentons une version par blocs, le rendant très
efficace en pratique. Le second est celui de Keller-Gehrig, pour
lequel nous avons montré que l'usage de la factorisation LSP est
particulièrement adaptée. Enfin une comparaison des performances
pratiques de ces deux algorithmes montrera que leurs domaines de
prédilection sont complémentaires et dépendent du nombre de sous
espaces invariants de la forme de Frobenius associée.