Calcul du rang et d'une base du noyau d'une matrice polynomiale

Nous réduisons le problème du calcul du rang et d'une base du noyau d'une matrice polynomiale d'une variable, à celui du produit de deux matrices polynomiales. Pour une matrice $n \times n$ de degré $d$ sur un corps $K$, nous proposons un algorithme (probabiliste certifié) qui requiert grosso modo (à des facteurs logarithmiques près) le même nombre d'opérations dans $K$ que le produit de deux matrices $n \times n $ de degré $d$.

Nous obtenons ce résultat en combinant une remontée de Hensel aux grands ordres avec une reconstruction de fraction matricielle, ainsi que grâce à un calcul de bases minimales (ou presque).

Avec en tête le rôle joué par l'exposant du produit de matrices en complexité algébrique de l'algèbre linéaire, cette étude complète la connaissance des liens entre le produit et les autres problèmes fondamentaux pour les matrices polynomiales.

[Bibliographie: A. Storjohann et G. Villard, RRLIP 2005-03, ENS Lyon]