ALGORITHME DE BAREISS, ALGORITHME DES SOUS-RÉSULTANTS

摘要

Bareiss' algorithm computes the determinant of a matrix. It eliminates in an optimal way the coordinates of its column vectors by fraction-free triangularisation. The subresultant algorithm also calculates the resultant and the greatest common divisor of two polynomials by eliminating optimally their coefficients. In this article, we relate these two algorithms in a single mathematical concept. Intrinsic aspects of this relation are emphasized, thus most of the calculations is avoided as they are long and complicated. Finally, we give a variation of the subresultant algorithm which makes the computation of the chain of the subresultant polynomials more "economical" (see section 6.2 page 23).%L'algorithme de Bareiss (calculant le déterminant d'une matrice) n'est autre qu'une méthode visant l'élimination optimale des composantes des vecteurs colonnes de cette matrice par triangularisation. L'algorithme des sous-résultants (calculant le résultant, mais aussi le pgcd, de deux polynômes) vise de même l'élimination optimale des coefficients de ces deux polynômes. L'objet de cet article est de réunir sous un même formalisme mathématique l'algorithme de Bareiss et celui des sous-résultants en insistant sur l'aspect intrinsèque des objets, et si possible, en évitant les complications calculatoires qui obscurcissent leurs exposés. Enfin, une variante de l'algorithme des sous-résultants sera proposée : son int╚êt est de calculer la chaîne des polynômes sous-résultants de façon « économique » (Voir section 6.2 page 23).