Multiplication rapide de polynômes
Bonjour,
Je connais la méthode de multiplication de polynômes par la transformée de Fourier rapide qui consiste à évaluer les polynômes en des racines nièmes de l'unité, puis multiplier les évaluations et enfin interpoler à partir de ces valeurs pour obtenir le résultat.
J'ai lu dans un livre une autre méthode qui utilise également la FFT. Le principe est le suivant: en notant $c_j=\sum_{k=0}^{j} a_kb_{j-k}$ le coefficient d'indice $j$ du produit d'un polynôme de degré $p$ et d'un polynôme de degré $q$, on peut écrire que $c$ est le produit de convolution de $a$ et $b$ et par propriété de la transformée de Fourier, en prenant $ N \geq p+q$, on obtient $c=F_N^{-1}(F_N(a)F_N(b))$.
Les deux méthodes ont la même complexité. Je me demandais donc si l'une d'entre elles était plus avantageuse que l'autre. J'ai l'impression que la première méthode est plus utilisée, en tout cas, c'est généralement celle-là que je vois dans les livres. Y a-t-il une raison?
Merci de votre aide.
Je connais la méthode de multiplication de polynômes par la transformée de Fourier rapide qui consiste à évaluer les polynômes en des racines nièmes de l'unité, puis multiplier les évaluations et enfin interpoler à partir de ces valeurs pour obtenir le résultat.
J'ai lu dans un livre une autre méthode qui utilise également la FFT. Le principe est le suivant: en notant $c_j=\sum_{k=0}^{j} a_kb_{j-k}$ le coefficient d'indice $j$ du produit d'un polynôme de degré $p$ et d'un polynôme de degré $q$, on peut écrire que $c$ est le produit de convolution de $a$ et $b$ et par propriété de la transformée de Fourier, en prenant $ N \geq p+q$, on obtient $c=F_N^{-1}(F_N(a)F_N(b))$.
Les deux méthodes ont la même complexité. Je me demandais donc si l'une d'entre elles était plus avantageuse que l'autre. J'ai l'impression que la première méthode est plus utilisée, en tout cas, c'est généralement celle-là que je vois dans les livres. Y a-t-il une raison?
Merci de votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Calculer la transformée de Fourier discrète d'un vecteur et évaluer le polynôme en les racines de l'unité.
Pour comprendre cela, il faut comprendre qu'un vecteur à n composantes est vu ici comme une fonction de $\mathbf Z/n$ dans $\mathbf C$ et expliciter l'isomorphisme entre $\mathbf Z/n$ et son dual $\widehat{(\mathbf Z/n)}$.