Factorisation LU creuse : Quelques mises à jour

Dans cette présentation je considèrerai des méthodes d'élimination pour calculer le rang de matrices creuses rectangulaires à coefficients dans un corps fini. L'idée est de trouver au préalable un large ensemble de pivots de Gauss sans effectuer d'opération arithmétique, ce qui permet de réduire le nombre d'étapes d'élimination. Après quelques rappels sur la factorisation LU creuse, je présenterai un nouvel algorithme inspiré de l'algorithme GPLU, et d'une heuristique de sélection de pivots utilisée lors du traitement de matrices issues du calcul de base de Gröbner. Ensuite, j'expliquerai comment nous avons amélioré cette heuristique afin de trouver un plus large ensemble de pivots sans effectuer d'opération arithmétique. Je présenterai enfin succinctement notre implémentation. Nos expériences montrent qu'elle peut calculer en cinq minutes le rang de matrices qui nécessitent plus de 15 jours avec les techniques précédentes.
Cet exposé est basé sur l'article http://cristal.univ-lille.fr/~bouillag/pub/CASC16.pdf, ainsi que sur nos travaux ultérieurs.