Pré-soutenance de thèse : Calcul exact avec des matrices quasiséparables et des matrices polynomiales à structure de déplacement

Cette thèse en algèbre linéaire exacte présente des algorithmes rapides pour le calcul du déterminant de matrices polynomiales à structure de
déplacement et une étude de formats de matrices quasiséparables.
Les matrices polynomiales à structure de déplacement ont une double structure liée à des polynômes bivariés. Les techniques de calcul de produit existant pour les matrices sur un corps s’appliquent aux matrices polynomiales avec un coût quasi-linéaire en la taille de l’entrée. Ce n’est pas le cas pour les techniques de calcul du
déterminant. Des avancées récentes ont permis de réduire le coût de ce calcul dans les cas des matrices de Sylvester et des matrices caractéristiques de matrices de multiplication modulaire. En élargissant le domaine d’application de ces deux algorithmes nous améliorons le coût du calcul du polynôme caractéristique de matrices quasi-Toeplitz et quasi-Hankel. Nous améliorons ensuite le coût du calcul du résultant bivarié en présentant un algorithme ayant nécessité l’analyse de la structure des matrices intervenant dans la remontée d’ordre élevé pour l’inverse d’une matrice de Sylvester afin d’adapter la technique des « pas de bébés, pas de géants » au calcul des termes de l’inverse de matrices polynomiales plus générales que les seules matrices caractéristiques.
Une étude comparative est aussi faite sous l’angle du calcul formel pour différents formats de stockage de matrices quasiséparables. Les formats HSS et SSS sont utilisés en calcul numérique, seuls les formats Bruhat et RRR avaient été étudiés pour le calcul exact. Sont présentés une adaptation des formats HSS et SSS à ce cadre et une nouvelle version de l’algorithme de compression Bruhat prenant en entrée une matrice sous format quelconque, pour utilisation dans le cas d’une matrice creuse et d’une matrice provenant de la somme de deux matrices sous format Bruhat. Les comparaisons se font en termes théoriques et pratiques, avec des implémentations dans la bibliothèque d’algèbre linéaire exacte fflas-ffpack.