Fourier-Transformation - Was soll das?

03.02.2007, 16:27	Auf diesen Beitrag antworten »
Chaosworld	Fourier-Transformation - Was soll das? Hallo Ich hatte noch nie mit der schnellen Fourier Transformation zu tun. Jetzt ist es leider ein recht grosser Bereich im Kurs "Paralelle Algorithmen". Ich beschreibe erst einmal, was ich verstanden habe und dann was ich nicht mehr verstehe. Also ich gebe Omega (w) vor, das ist bei n=4 z.B. i. soweit klar, auch wenn ich mir vorstelle, dass es bei steigendem n immer schwerer wird, Omega zu bestimmen. Egal. Aus Omega kann ich das F bestimmen durch fij=w^(ij). Soweit auch klar. Jetzt habe ich also den Wert a und berechne durch b=Fa. Soweit auch noch klar. Durch die besonderheit von w kann man das verkürzen und kommt anstatt O(n^2) auf nur O(n log(n)). Soweit alles klar. Aber mein Problem: Warum macht man das überhaubt???? Ich meine ich könnte ja genausogut eine Funktion erstellen, mit der ich schneller +6 berechne, aber wenn ich das garnicht benötige bringt mir das doch garnichts. Ich stell es mir gerade so vor: ich möchte xy berechnen. Beides sind Vektoren, mit sagen wir n=4. Anstatt also xy zu berechnen, rechne ich: (Fx)(Fy) und dann rechte ich das mal F^-1 (die Umkehrfunktion) original habe ich bei xy doch O(n^2) und bei Fx habe ich durch die FFT nur noch O(n log(n)) und bei Fy das selbe, also O(n log(n)) und die beiden werte muss ich jetzt multiplizieren, und dass dauert doch dann wieder O(n^2) und dann noch die inverse F. Ich habe also doch nichts gewonnen, sondern nur ein paar "unnütze" Rechnungen hinzugefügt. Ich hoffe ich habe richtig erklärt, was mein Problem ist. Im vorraus danke für jede Antwort. Chaosworld PS.: wurde von www.matheboard.de hierhin verweist.


03.02.2007, 17:12	Auf diesen Beitrag antworten »
Tobias	Ich glaube dein Denkfehler besteht darin, dass FFT(x)FFT(y) die Komplexität O(nlogn) + O(n^2) haben soll, weil Multiplikation O(n^2) ist. Hier ist aber gerade die Idee der FFT: Wir formen gerade so um, dass FFT(x)FFT(y) punktweise, d.h. nur komponentenweise multipliziert werden muss. Das ist aber O(n). So kommt man insgesamt auf O(nlogn): $[latex]\alpha = (\alpha_1, \ldots, \alpha_n), \beta = (\beta_1, \ldots, \beta_n)[/latex]$ $[latex]\alpha^\ast = FFT(\alpha), \beta^\ast = FFT(\beta)[/latex]$ $[latex]\alpha\cdot\beta = FFT^{-1}(\alpha^\ast \cdot \beta^\ast)[/latex]$ $[latex](\alpha^\ast \cdot \beta^\ast)_k = \alpha_k^\ast \cdot \beta_k^\ast[/latex]$ Ich hoffe das erklärt dein Problem.
03.02.2007, 18:13	Auf diesen Beitrag antworten »
Chaosworld	Hi Tobias danke für deine Antwort. Also ich hatte schon die Vermutung, dass sich irgendwie die Komplexität reduziert. Nur das wie verstehe ich noch nicht wirklich. Ich versuche einfach mal ein einfaches Beispiel zu machen: n=4 a=(5,8,3,2) b=(7;6;4;1) Dann ist doch abT=57+86+34+21=97 berechnet mit 4 multiplikationen. Und jetzt mache ich das selbe mit FFT: FaT= 1__1__1__1 1__ i__-1__-i 1__-1__1__-1 1__-i__-1__i (5,8,3,2)T =(18,2,-2,2)T das selbe mit bT ergibt: (18,3,4,3) ok jetzt berechne ich FFT(a)FFT(b)= 324__54__72__54 36___ 6__8___6 -36__-6__-8___-6 36___6__8___6 ok das jetzt mit F^-^multiplizieren ergibt dann: 1/4__1/4__1/4__1/4 1/4__ i/4__-1/4__-i/4 1/4__-1/4__1/4__-1/4 1/4__-i/4__-1/4__i/4 * 324__54___72___54 36___ 6____8____6 -36___-6___-8___-6 36____6____8___6 = 360___60___80___60 360___60___80___60 216___36___48___36 360___60___80___60 Sorry aber das ist irgendwie GANZ anders als 97??? ODER??? Also irgendwie ist da bei mir der Groschen noch nicht gefallen wie es mir scheint. Hoffe mir kann das jemand erklären. Danke für jede Antwort Chaosworld
03.02.2007, 18:24	Auf diesen Beitrag antworten »
Tobias	Sagmal, wie ist denn bei dir überhaupt die Multiplikation von den zwei Vektoren definiert? Ich dachte du meinst hier die Multiplikation zweier Polynome, deren Koeffizienten in einem Tupel zusammengefasst wurden. Die Multiplikation von zwei Vektoren (wobei du den einen transponierst) ist ja auch nicht O(n^2) sondern O(n). Ich dachte an zwei Polynome: $[latex]\sum_{i=0}^n \alpha_ix^i \cdot \sum_{i=0}^m \beta_ix^i[/latex]$ Das Ergebnis ist wieder ein Polynom. Das stellt man dar als $[latex](\alpha_1, ..., \alpha_n) \cdot (\beta_1, ..., \beta_m) = (\gamma_1, \ldots, \gamma_p)[/latex]$ Hier ist das Ergebnis der Multiplikation auch kein Skalar sondern wieder ein Vektor. Darauf kann man dann FFT^-1 anwenden.
Anzeige

03.02.2007, 18:27	Auf diesen Beitrag antworten »
Chaosworld	ach sooooo, jetzt sehe ich das Problem, hmmmmmm muss ich noch einmal durchdenken, ob das dann richtig klappt, habe einfach die normale Matrix-Multiplikations-Regeln angewendet
03.02.2007, 18:50	Auf diesen Beitrag antworten »
Chaosworld	ok verfolge ich das einfach noch mal weiter mal sehen wo es mich hinbringt :-D Also ich habe wieder a=(5,8,3,2) b=(7;6;4;1) was bedeutet: 5x^3+8x^2+3x^1+2 ... also wäre die multiplikation von beiden= 57x^6+(56+78)x^5 ... usw ok soweit klar oder genereller geschrieben: $[latex]c_k=\sum_{j=0}^k~a_j*b_{k-j}[/latex]$ jetzt soll dass also mit FFT einfacher werden, also muss ich FFT(a) anwenden, hm da hackt es bei mir jetzt, irgendwie kann ich jetzt nicht mehr vernünftig FFT(a) bestimmen.
03.02.2007, 19:17	Auf diesen Beitrag antworten »
Chaosworld	also bei mir im Script steht nur das hier: $[latex]Fc[i]=c'_i=\sum_{k=0}^{2n-1}~\omega^{ik}\cdot c_k[/latex]$ $[latex]=\sum_{k=0}^{2n-1}~\omega^{ik} \cdot \sum_{k=0}^{2n-1}~a_k\cdot b_{k-j}[/latex]$ denn: c=a*b; aj,bj=0 für j >= n $[latex]=\sum_{j, 1\geq 0}~\omega^{ij}a_j\cdot \omega^{il}b_l[/latex]$ (Substitution j-l=k <= 2n-1) $[latex]=\sum_{j=0}^{2n-1}~\omega^{ij}a_j \cdot \sum_{l=0}^{2n-1}~\omega^{il}b_l[/latex]$ Dass das korrekt ist, ist ja einleuchtend und auch einfach nachzuvollziehen. Bei mir harpert es glaube ich nur noch an den Punkt, wie ich FFT(a), bzw. FFT(b) berechnen muss.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »