exercice de complexité: calcul de résultant

Forum pour les étudiants de la préparation agreg option C de Grenoble

Modérateur : xcasadmin

parisse
Messages : 5112
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

exercice de complexité: calcul de résultant

Message par parisse » 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

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 nécessaire, les beta_j sont pris dans une extension du corps fini).
Si on effectue la division euclidienne de A par B

Code : Tout sélectionner

A=B*Q+R 
on a A(beta_j)=R(beta_j), on peut donc en déduire que

Code : Tout sélectionner

resultant(A,B)=(-1)^(degre(A)*degre(B))*lcoeff(B)^(degree(A)-degree(R))*resultant(B,R)
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.

Répondre