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.