Transformée de Fourier rapide en utilisant une matrice Vandermonde - Évaluation des Coefficients?

Question

Disons que je suis en train d'évaluer l'polynomiale:

x^2 + 1

Utilisation de la transformée de Fourier rapide méthode d'évaluation des coefficients. Maintenant, je peux changer cela en forme matrice / vecteur en utilisant la co-effcient comme entrées pour la transformée de Fourier rapide:

:

x^2 + 1 = <1, 0, 1, 0>

Ceci est fait en utilisant la valeur de coefficient par exemple 1 = 1, 0x ^ 1 = 0, X ^ 2 = 1 et ainsi de suite

Maintenant, nous arrivons à peu où je suis totalement confus. Je voulais utiliser la matrice Vandermonde: matrice Vandermonde ~ Wiki pour évaluer ces valeurs dans FFT formulaire en utilisant la matrice:

1 1 1 1  
1 i-1-i
1-1 1-i
1-i 1 i

La sortie de

fft(1,0,1,0)

est

(2,0,2,0)

Maintenant ce l'étape que je ne comprends pas tout à fait, comment utiliser cette matrice-nous pour obtenir (2,0,2,0)?

Answer 1

D'abord, votre matrice Vandermonde est incorrecte. Le (4,3) -1 entrée doit être, non pas une, étant donné que la quatrième ligne devrait être (-i) ⁰ , (-i) ¹ , (-i ) ² , (-i) ³ . Notez en particulier que

(- i) *. (- i) = (-1) ² * i ² = i ² = -1

Grâce à cette correction, le résultat résulte de la multiplication de la matrice de Vandermonde par le vecteur de colonne (1,0,1,0).

Answer 2

Peut-être pourriez-vous expliquer ce que votre objectif global est ici. Je ne l'ai jamais entendu parler de TFR utilisés pour évaluer polynômes. Ils sont utilisés pour multiplier polynômes, ou convoluer signaux (une tâche équivalente), mais je ne voudrais pas déranger à moins que les polynômes / signaux ont un grand nombre de termes. x ² + 1 n'est pas grande. 16 termes est pas grande, et même 64 ou 256 termes est probablement mieux réalisé par simple O (N ² ) techniques.

transformées de Fourier discrètes utiliser la matrice M _ij = ω ^ij , où ω est la racine nième de complexe 1 et de la colonne / ligne de numérotation va de 0 à N-1.

Transformées de Fourier rapide ne jamais utiliser cette matrice directement, ils sont fortement optimisés pour utiliser une technique de division et Conquer ( Cooley-Tukey algorithme ) pour calculer le résultat final par des étapes de 2x2 TFD en série et en parallèle.

Si vous écrivez votre vecteur [0,1,0,1] au lieu de [1,0,1,0], je pense que vous verrez que si vous multipliez par la matrice que vous avez donné, vous obtiendrez [0,2,0,2]. (Même si vous avez une erreur, il est

1 1 1 1  
1 i-1-i
1-1 1-1
1-i-1 i

) Il utilisez doit être une convention dans le programme qui inverse l'ordre des coefficients du vecteur.