Algorithmes de calcul de la réduction de Hermite d'une matrice a coefficients polynomiaux

avec Labhalla S., Marlin R. Theoretical Computer Science 161 (1996), 69-92.

Résumé : Nous étudions dans cet article des algorithmes de calcul de la réduction de Hermite d'une matrice à coefficients polynomiaux, qui évitent l'explosion de la taille des objets intermédiaires et ont une bonne complexité séquentielle. Le deuxième et le troisième algorithmes généralisent la méthode des sous-résultants pour le calcul du pgcd de deux polynômes. Le dernier de ces algorithmes semble optimal en ce sens qu'il calcule une réduction de Hermite avec une matrice de passage de degré minimal, en utilisant une méthode progressive et économique. Nous ramenons le calcul de la réduite de Hermite à un problèmes de triangulation progressive de matrices dont les tailles sont bien contrôlées et dont les entrées sont des coefficients des polynômes donnés en entrée. L'algorithme est donc faisable dès qu'on dispose d'une méthode de triangulation en temps polynomial pour les matrices dans le corps des coefficients. Il revient au même de dire que le calcul des déterminants est en temps polynomial dans le corps en question (pour le codage choisi). Les résultats théoriques sont meilleurs que pour les algorithmes connus précédemment, et les résultats pratiques sont encourageants.

Abstract : In this paper, we study some algorithms for computing an Hermite reduction of a matrix with polynomial entries which avoid the swell-up of the size of intermediary objects and have a good sequential complexity. The second and the third algorithms generalize the sub-resultant method for computing the gcd of two polynomials. The last one is optimal in the sense that it computes an Hermite reduction with a minimal degree change of basis matrix. The Hermite reduction with polynomials entries amounts to a linear algebra problem over the coefficient field with a good control of the dimensions. Our problem of linear algebra is a progressive triangulation of matrices. So it is feasible exactly when there exists a polynomial time algorithm computing determinants of matrices with entries in the coefficient field of the polynomials given as input. Theoreticals results are better than for previously known algorithms, and practical results are interesting.