Complexité du calcul de la transformée de Fourier discrète?

18

Quelle est la complexité (sur la RAM entière standard) du calcul de la transformée de Fourier discrète standard d'un vecteur de nombres entiers?n

L' algorithme classique pour les transformées de Fourier rapides , attribué de manière inappropriée [1] à Cooley et Tukey, est généralement décrit comme fonctionnant en temps . Mais la plupart des opérations arithmétiques exécutées dans cet algorithme complexe commencent par ième racines de l' unité, qui sont (pour la plupart ) évaluation irrationnelle, donc exacte en temps constant est pas raisonnable. Le même problème se pose avec l' algorithme naïf (multipliant par une matrice de Vandermonde de racines complexes d'unité).nO(nlogn)nnO(n2)

Il n'est même pas clair comment représenter exactement la sortie de la DFT (sous toute forme utile). En d'autres termes, il n'est pas clair que le calcul des DFT soit réellement possible!

Supposons donc que nous ayons seulement besoin de bits de précision dans chaque valeur de sortie. Quelle est la complexité du calcul de la transformée de Fourier discrète, en fonction de et ? (Pour être concret, n'hésitez pas à supposer que est une puissance de )bnbn2

Ou chaque exemple de "FFT" dans la littérature signifie-t-il réellement " transformation rapide de la théorie des nombres "? [2]

Voir mes questions connexes sur la complexité de l'élimination gaussienne et les plus courts chemins euclidiens .

[1] Il faut vraiment l'appeler (un préfixe de) l'algorithme de Gauss-Runge-König-Yates-Stumpf-Danielson-Lánczos-Cooley-Tukey.

[2] Et si oui, pourquoi la plupart des manuels décrivent-ils uniquement l'algorithme des nombres complexes?

Jeffε
la source
1
Je pense que c'est son point: en théorie, vous n'avez pas à vous soucier de , mais dans toute mise en œuvre RÉELLE, vous devez vous en soucier et de l'erreur qui pourrait être encourue. b
Suresh Venkat
1
En fait, c'est une bonne question chaque bit de précision supplémentaire ajoute à la force du signal (multiplier par ). Je pense donc que la question sera plus utile si les tailles de mots intermédiaires peuvent être développées! 3dB2
vs
3
L'analyse calculable a tenu compte de cela et des questions connexes. Cet article produit une complexité liée au calcul de la transformée de Fourier dans le cadre de l'effectivité de type II de Weirauch. La limite est qu'elle est linéaire dans la présentation de l'entrée (infinie, à valeur réelle). L'entrée et la sortie sont des paramètres de précision définis par rapport à ce système, il peut donc y avoir un moyen de les traduire dans le modèle de RAM.
Aaron Sterling,
3
Jetez un oeil à la méthode A dans l'article de Schönhage et Strassen sur la multiplication entière. Il utilise des transformées de Fourier complexes avec une précision limitée. Je pense que cela est également décrit dans Knuth Vol. 2.
Markus Bläser
2
Markus, Aaron: convertir en réponses?
Suresh Venkat

Réponses:

9

Cette réponse est une variante de l'analyse du premier algorithme ("Methode A") de Schönhage et Strassen pour la multiplication des entiers longs.

Supposons que nous voulons calculer une FFT de longueur . Mettez votre entrée à l'échelle de sorte que toutes les valeurs soient inférieures à 1. Supposons d'abord que nous calculons avec arithmétique à points fixes à bits ( bits après le point binaire). Soit l'unité ("complexe") de moindre position. Soit . m m δ = 2 1 / 2 - m ω = exp ( 2 π i / K )K=2kmmδ=21/2mω=exp(2πi/K)

1) On peut calculer des approximations telles que pour tous les . Cela peut être fait dans le temps où est le temps nécessaire pour multiplier les nombres à bits. (voir Knuth Vol.2, 3e éd., page 309). | ω j - ω j | ( 2 k - 1 ) δ 0 j K - 1 O ( K M ( m ) ) M ( m ) mωj|ωjωj|(2k1)δ0jK1O(KM(m))M(m)m

Si la RAM entière standard signifie un coût logarithmique, alors . Si la RAM entière standard signifie le mot RAM, alors . (Schönhage et Strassen montrent dans "Methode A" comment réduire en temps linéaire la multiplication des nombres bits en multiplication des nombres de bits . Ce dernier peut être fait à des coûts unitaires.)M ( m ) = O ( m ) m m O ( log m )M(m)=O(mlogm)M(m)=O(m)mmO(logm)

2) La FFT classique de Cooley-Tukey calcule des opérations de la forme . Nous utilisons l' arithmétique à virgule fixe à bits, ces options deviennent . Si nous connaissons et jusqu'à une erreur de , nous obtenons jusqu'à une erreur de .m a = t r u n c a t e ( b + ω j c ) b c ϵ a 2 ϵ + 2 k δa=b+ωjcma=truncate(b+ωjc)bcϵa2ϵ+2kδ

3) En utilisant l'induction, il est facile de voir que nous obtenons le résultat final avec une erreur . Pour obtenir la précision à la fin, . b m k + log k + b + O ( 1 )(2k1)2kδbmk+logk+b+O(1)

4) Ainsi, le temps de course final est .O(KkM(k+b))

Cela devrait également fonctionner avec des nombres à virgule flottante: 1) peut toujours être fait avec l'arithmétique à virgule fixe, 2) est également vrai pour les nombres à virgule flottante.


En arithmétique à virgule fixe, je pense que cela peut même être fait plus rapidement. D'abord, nous réduisons le calcul de la FFT à la multiplication des polynômes en utilisant l'astuce de Bluestein. La longueur des coefficients nécessaires pour obtenir la précision souhaitée doit être . Ensuite, nous réduisons la multiplication des polynômes à la multiplication des entiers longs. (Ajoutez les coefficients à un nombre long et séparez-les par des blocs de zéro de longueur .) La longueur des entiers est .O ( k + b ) O ( K ( k + b ) )O(k+b)O(k+b)O(K(k+b))

Markus Bläser
la source
Donc, à partir du point (4), en définissant K = n et b = O (log n), et en supposant que nous fonctionnons sur le mot RAM, nous obtenons un temps d'exécution de . Droite? O(nlog2n)
Jeffε
Oui. Le deuxième algorithme donne même , en supposant que la précision O ( k + b ) est suffisante. (Je ne vois pas pourquoi ce n'est pas suffisant, mais je n'ai pas fait les détails.)O(nlogn)O(k+b)
Markus Bläser
2
BTW, si est aussi petit que O ( log n ) , le premier algorithme donne également le temps d'exécution O ( n log n ) puisque M ( O ( log n ) ) = 1 . bO(logn)O(nlogn)M(O(logn))=1
Markus Bläser
Il m'est arrivé de regarder le livre d'Aho, Hopcroft et Ullman sur "La conception et l'analyse des algorithmes" et ils discutent en détail de l'algorithme dans le modèle de bits et des problèmes connexes.
Chandra Chekuri,
Mais pour autant que je m'en souvienne, ils ne discutent que de la "FFT théorique" dans le modèle binaire.
Markus Bläser
8

Ce n'est pas une réponse complète, mais je peux vous indiquer quelques articles pertinents et expliquer en partie pourquoi il n'est pas si facile d'extraire une réponse à votre question spécifique de la littérature.

Permettez-moi de commencer par demander, pourquoi voulez-vous connaître la réponse à cette question? En règle générale, les personnes qui se soucient de ce type de problème sont celles qui sont réellement confrontées à la mise en œuvre d'une FFT haute performance pour une application pratique. Ces personnes se soucient moins de la complexité asymptotique dans certains modèles de calcul idéalisés que de la maximisation des performances sous leurs contraintes matérielles et logicielles particulières. Par exemple, les développeurs de la transformation de Fourier la plus rapide de l'Ouest écrivent dans leur article:

Le meilleur choix dépend des détails du matériel comme le nombre de registres, la latence et le débit des instructions, la taille et l'associativité des caches, la structure du pipeline de processeur, etc.

Ce sont des problèmes que les théoriciens ne veulent généralement pas souiller, mais ils sont d'une grande importance dans les implémentations réelles. Si un théoricien déclare: «J'ai trouvé la meilleure complexité absolue des bits asymptotiques dans le modèle RAM», le praticien pourrait dire: «C'est bien», mais peut trouver un tel résultat théorique inutile à ses fins.

Cela dit, je pense que votre meilleur pari est de regarder la littérature sur l'analyse numérique. Par exemple, Tasche et Zeuner ont examiné de près la stabilité numérique de l'algorithme FFT. Ce n'est peut-être toujours pas exactement ce que vous voulez, car le consensus général parmi les praticiens semble être que pour atteindre une certaine précision numérique, la meilleure approche pratique consiste à précalculer certains nombres appelés «facteurs de torsion» avec une grande précision. Si vous ne faites qu'une seule FFT, ce ne sera pas l'approche la plus rapide car vous n'aurez pas à amortir le coût de votre précalcul ponctuel sur un grand nombre de calculs FFT. Pourtant, leur analyse de l'erreur d'arrondi la plus défavorable devrait toujours être pertinente pour votre question.

Timothy Chow
la source
Je parie que les gens seraient intéressés de savoir s'ils peuvent presser bit de précision supplémentaire, disons s'ils peuvent faire une FFT de 1024 points (OFDM dans les WLAN), disons 100 multiplications supplémentaires sur les algorithmes actuels. 11024100
vs
1
Je m'intéresse à une question purement théorique, dans l'intérêt d'une érudition correcte et honnête. Il est assez courant de lire "et ici, nous utilisons une FFT, qui, comme tout le monde le sait, s'exécute en temps O (n log n)" au milieu d'un algorithme autrement purement combinatoire, sinon analysé en termes de parcours de pointeurs et O (log n arithmétique entière) bits. Si, en fait, une convolution entière peut être effectuée en temps O (n log n) en utilisant une légère variante de la FFT, c'est peut-être pardonnable mais toujours bâclé. Sinon, tout pauvre schmuck qui essaie d'implémenter l'algorithme va obtenir LA FAUTE RÉPONSE.
Jeffε
Et bien sûr, je ne m'attends pas à ce que la réponse à ma question ait un quelconque impact dans la pratique.
Jeffε
2
Jeff, en ce qui concerne l'érudition honnête, ne suffit-il pas de dire que la FFT nécessite des opérations d'anneau O (n log n)? C'est la manière naturelle de mesurer la complexité de l'algorithme FFT. Je ne vois pas la motivation pour tout convertir en un modèle particulier de calcul. Y a-t-il un théorème que vous essayez de prouver où il est crucial de garder une trace du nombre de bits de précision? Quant à votre pauvre schmuck, je n'achète pas qu'il obtiendra la «mauvaise réponse». Dans toute mise en œuvre réelle, la question que vous posez ici est très peu susceptible d'être la préoccupation dominante.
Timothy Chow,
Tim: Bien sûr, il suffit de dire les opérations d'anneau si vous analysez la FFT isolément. Mais si la FFT n'est qu'un composant d'un algorithme plus grand, le rapport du temps d'exécution de l'algorithme plus grand nécessite un modèle de calcul cohérent pour tous ses sous-programmes constitutifs, y compris la FFT. Par exemple, "convoluer les deux séquences entières en utilisant l'algorithme Cooley-Tukey FFT puis insérer les coefficients résultants dans une table de hachage" (pour constituer un exemple totalement faux) demande des ennuis. O(nlogn)
Jeffε