Fourier-Transformation - Was soll das? |
Chaosworld
Grünschnabel
Dabei seit: 03.02.2007
Beiträge: 5
|
|
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^(i*j). Soweit auch klar. Jetzt habe ich also den Wert a und berechne durch b=F*a. 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 x*y berechnen. Beides sind Vektoren, mit sagen wir n=4. Anstatt also x*y zu berechnen, rechne ich:
(F*x)*(F*y)
und dann rechte ich das mal F^-1 (die Umkehrfunktion)
original habe ich bei x*y doch O(n^2)
und bei F*x habe ich durch die FFT nur noch O(n log(n))
und bei F*y 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 16:27 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
|
03.02.2007 17:12 |
|
|
Chaosworld
Grünschnabel
Dabei seit: 03.02.2007
Beiträge: 5
|
|
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 a*bT=5*7+8*6+3*4+2*1=97
berechnet mit 4 multiplikationen.
Und jetzt mache ich das selbe mit FFT:
F*aT=
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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Chaosworld: 03.02.2007 18:25.
|
|
03.02.2007 18:13 |
|
|
Chaosworld
Grünschnabel
Dabei seit: 03.02.2007
Beiträge: 5
|
|
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:27 |
|
|
Chaosworld
Grünschnabel
Dabei seit: 03.02.2007
Beiträge: 5
|
|
|
03.02.2007 19:17 |
|
|
|