Calculer le polynôme caractéristique d'une matrice en complexité optimale

Le calcul matriciel est un outil fondamental des sciences et techniques, qui apparaît dès qu'il s'agit de traiter de problèmes qui sont intrinsèquement linéaires ou bien qui peuvent s'y ramener par approximation. Cet outil, au cœur du calcul scientifique et du calcul formel, est étudié en informatique avec comme objectifs l'amélioration de la complexité des calculs et le développement d'implantations logicielles haute performance. Ces efforts sont motivés par de nombreuses applications qui dans le cadre du calcul formel proviennent par exemple de la robotique, de la biologie, des mathématiques expérimentales, ou encore de la cryptographie. En outre, ces applications demandent souvent de réaliser des calculs sur des matrices de très grande taille et représentées de manière exacte (les coefficients sont dans un corps fini, ou sont des nombres entiers ou rationnels).

Historiquement, de nombreuses opérations sur des matrices n x n ont été réalisées en complexité cubique O(n³) : multiplication, élimination de Gauss, résolution de systèmes linéaires, déterminant, inversion, rang, etc. En 1969, un changement de paradigme a eu lieu, avec l'introduction par Strassen d'algorithmes récursifs pour multiplier et inverser des matrices en temps sous-cubique. Le produit de matrices n'a cessé de connaître des améliorations jusqu'à aujourd'hui, et de nombreuses réductions algorithmiques ont permis de mieux relier les différentes opérations entre elles et mieux cerner leurs difficultés respectives. Ainsi, ces opérations peuvent être calculées avec le même coût qu'un produit de matrices, et pour plusieurs d'entre elles il a été montré que ce coût est optimal : on ne peut pas descendre en dessous. La méthode de Strassen ainsi que les réductions sont aujourd'hui des pierres angulaires des bibliothèques logicielles de pointe en calcul matriciel. 

Le polynôme caractéristique d'une matrice carrée A est défini comme le déterminant de la matrice polynomiale x Id - A, où x est une nouvelle variable. Il fournit des informations précieuses sur certains invariants de A et sur les polynômes qui annulent A. C'est par exemple pour ces raisons qu'il est calculé dans la résolution de systèmes polynomiaux multivariés, dont c'est une étape coûteuse à cause de la très grande taille de A.

Au début des années 1980, c'était la dernière des opérations matricielles de base qui avait une complexité cubique et ne jouissait pas d'une réduction efficace au produit matriciel. En 1985, Keller-Gehrig a donné une telle réduction, mais avec une complexité encore supérieure à celle du produit par un facteur logarithmique. Depuis lors, les seuls algorithmes s'affranchissant de ce surcoût reposaient soit sur des hypothèses de généricité du problème, soit sur des algorithmes probabilistes imposant en particulier des contraintes sur le corps des coefficients de la matrice.

Le nouvel algorithme, proposé par les chercheurs et dont la publication a été primée par le Best Paper Award du Journal of Complexity, est déterministe et son temps d'exécution est le même que celui d'un produit de matrice, sans hypothèse sur le corps. Pour ce faire, l'algorithme recourt à l'arithmétique rapide des polynômes et des matrices polynomiales, en exploitant des résultats très récents sur le sujet et en explorant un cheminement nouveau dans les compromis dimension/degré jusqu'alors utilisés. Le résultat obtenu concerne plus généralement le calcul de déterminant pour une grande famille de matrices polynomiales à une variable, les matrices dites "réduites". Outre la complexité optimale, une implémentation de cet algorithme s'avère avoir de meilleures performances que l'état de l'art pour cette tâche, en particulier sur les petits corps finis.

Publication : Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Vincent Neiger, Clément Pernet