6章 FFT

アルゴリズム

ωn = 1の原始n乗根
n乗して初めて1になる数。

  • n=2:-1
  • n=3:(-1±√(3)i)/2
  • n=4:±i
  • n=5:5個

離散フーリエ変換(Discrete Fourier Transform)

入力x=(x0,x1,x2,…,xn-1)
出力y=Ax Aはn次正方行列。
単純な計算を行うとO(n^2)となる。

たたみこみ(convolution)

a \otimes b = (c_0,c_1,...,c_{2n-2})
c_i=\sum_{k=0}^i a_k b_{i-k}
例：多項式の掛け算

高速フーリエ変換(Fast Fourier Transform)※アルゴリズムの名前

DFTは問題の名前
入力:x(n次元ベクトル)
出力:y=Ax(n次元ベクトル)
y_i=\sum_{k=0}^{n-1}x_kw_n^{ik} (i=0,1,...,n-1)