Informatiker Board | Theoretische Informatik | Fourier-Transformation

Informatiker Board » Themengebiete » Theoretische Informatik » Fourier-Transformation - Was soll das?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Fourier-Transformation - Was soll das?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Chaosworld
Grünschnabel

Dabei seit: 03.02.2007
Beiträge: 5

Fourier-Transformation - Was soll das?

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie Chaosworld in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Ich glaube dein Denkfehler besteht darin, dass

FFT(x)*FFT(y) die Komplexität O(n*logn) + 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(n*logn):

$[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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 03.02.2007 17:18.

03.02.2007 17:12

Nehmen Sie Tobias in Ihre Freundesliste auf

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

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 03.02.2007 18:26.

03.02.2007 18:24

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

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:
5*x^3+8*x^2+3*x^1+2 ...
also wäre die multiplikation von beiden=
5*7*x^6+(5*6+7*8)*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.

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Chaosworld: 03.02.2007 19:01.

03.02.2007 18:50

Chaosworld
Grünschnabel

Dabei seit: 03.02.2007
Beiträge: 5

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Chaosworld: 03.02.2007 19:17.

03.02.2007 19:17

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Fourier-Transformation - Was soll das?