2.2.1 Algorithmus zur Fast Fourier Transformation

• Problem: Auswertung von Summen der Form
  

  $$\beta_j = {1 \over N} \sum_{k=0}^{N-1} f_k e^{-2\pi i {j k \over N}}, \ \ \ \ \ \ \ \ \ j=0,1,\cdots,N-1$$ (2.25)

  
  
  $\Order(N^2)$ Multiplikationen!

  Definiere $W = e^{2 \pi i \over N}$ $\beta_j = \sum_{k=0}^{N-1} W^{jk} f_k$ Matrix mal Vektor, d. h. pro Zeile N Multiplikationen in N Zeilen.

• FFT (Fast Fourier Transformation) benötigt nur $\Order(N \log(N))$ Multiplikationen
• Prinzip: Darstellung von N als Produkt $N_1 \cdot N_2 \cdot N_3 \cdots N_n$, dann Reduktion auf kleinere Probleme der Größe N_m
• Höchste Effizienz für N=2ⁿ mit n > 0 (ganz)
• Verfahren: (Sande, Tukey 1966)
  • Definition:
    

    $$\epsilon_n = \exp{\left( {2 \pi i \over 2^n}\right)}$$ (2.26)

    
    

  • Damit lassen sich die Koeffizienten schreiben:
    

    $$N \beta_jt = \sum_{k=0}^{N-1} f_k \epsilon_n^{j k}$$ (2.27)

    
    
    wobei $j = 0, 1, \cdots N-1$
  • Aufspaltung der Summen in geraden (j=2h) und ungeraden Anteil (j=2h+1)
  • Zusammenfassung der ,,komplementären Terme'' $f_k \epsilon_n^{jk}$ und $f_{k+M} \epsilon_n^{n(k+M)}$ wobei $k=0,1,\cdots, M-1$ mit $M := {N\over 2}$
  • Man erhält Summen halber länge. Mit $\epsilon_n^2 = \epsilon_{n-1}$ und $\epsilon_n^M = -1$ erhält man:

    
    

    $$N \beta_{2h} = \sum_{k=0}^{N-1} f_k \epsilon_n^{2hk} = \sum_{k=0}^{M-1} \underbrace{(f_k + f_{k+M})}_{f'_k} \epsilon_{n-1}^{hk}$$ (2.28)

    $$N \beta_{2h+1} = \sum_{k=0}^{N-1} f_k \epsilon_n^{(2h+1)k} = \sum... ...( \underbrace{(f_k - f_{k+M}) \epsilon_n^k}_{f''_k} \right) \epsilon_{n-1}^{hk}$$ (2.29)

    
    

  • Diese Summen lassen sich analog weiter verkürzen, so daß man mit $m = n, n-1, \cdots, 0$ und den Abkürzungen M:=2^m-1 und R:= 2^n-m:
    

    $$N \beta_{j R+r} = \sum_{k=0}^{2M-1} f_{r,k}^{(m)} \epsilon_m^{jk}$$ (2.30)

    
    
    mit $r=0,1,\cdots, R-1$ und $j= 0,1,\cdots, 2M-1$ sowie der rekursiven Definition der f_r,k^(m) ausgehend von den Startwerten f_0,k⁽ⁿ⁾ := f_k
    

    f_r,k^(m-1) = f_r,k^(m) + f_r,k+M^(m) (2.31)

    $$f_{r+R,k}^{(m-1)} = f_{r,k}^{(m)} - f_{r,k+M}^{(m)} \epsilon_m^k$$ (2.32)

    
    

  • Die gesuchten Koeffizienten ergeben sich dann zu
    

    $$\beta_r = {1 \over N} f_{r,0}^{(0)}$$ (2.33)

    
    

  • Problem bei der konkreten Implementation: Das Arbeiten mit zwei unabhängigen Arrays zur Speicherung aller Werte f_*,*^(m) benötigt ausgesprochen viel Platz. Effizientere Speicherverwaltung nötig! Man kann mit einem Array auskommen. (S. Stoehr I, S. 87ff)