exercice de complexité: calcul de résultant
Publié : mar. avr. 14, 2020 11:17 am
On se donne 2 polynomes A et B à coefficients dans un corps fini.
La définition de r=résultant de A et B comme le déterminant de la matrice de Sylvester donne un premier algorithme pour calculer r. Il existe une autre méthode de calcul qui utilise l'algorithme d'Euclide. On part du résultat suivant, où lcoeff(B) désigne le coefficient dominant de B
(si nécessaire, les beta_j sont pris dans une extension du corps fini).
Si on effectue la division euclidienne de A par B
on a A(beta_j)=R(beta_j), on peut donc en déduire que
Ce qui permet de calculer resultant(A,B) en suivant l'algorithme d'Euclide.
Comparer les complexités du calcul de resultant(A,B) par le déterminant de la matrice de Sylvester et par l'algorithme d'Euclide (on suppose que le cout d'une operation sur le corps fini est en O(1)). Illustrer sur machine.
La définition de r=résultant de A et B comme le déterminant de la matrice de Sylvester donne un premier algorithme pour calculer r. Il existe une autre méthode de calcul qui utilise l'algorithme d'Euclide. On part du résultat suivant, où lcoeff(B) désigne le coefficient dominant de B
Code : Tout sélectionner
resultant(A,B)=(-1)^(degre(A)*degre(B))*lcoeff(B)^degree(A)*produit sur les racines beta_j de B des A(beta_j)
Si on effectue la division euclidienne de A par B
Code : Tout sélectionner
A=B*Q+R
Code : Tout sélectionner
resultant(A,B)=(-1)^(degre(A)*degre(B))*lcoeff(B)^(degree(A)-degree(R))*resultant(B,R)
Comparer les complexités du calcul de resultant(A,B) par le déterminant de la matrice de Sylvester et par l'algorithme d'Euclide (on suppose que le cout d'une operation sur le corps fini est en O(1)). Illustrer sur machine.