円周率.jp (http://xn--w6q13e505b.jp/method/fft/index.html)

FFT

高速フーリエ変換(FFT ; Fast Fourier Transform) は数列 $\{a_j\}$ に対する離散フーリエ変換 (DFT ; Discrete Fourier Transform) や,その逆演算となる逆離散フーリエ変換 (IDFT ; Inverse DFT) を高速に計算するアルゴリズムであり, $O(n\log n)$ の計算量で DFT の結果を得られることが知られている. これを利用することで多倍長の乗算を $O(n\log n)$ で行うことができる.[JW07]

なお,DFT や IDFT の定義式については回転子 $\omega$ の回転方向や正規化のための係数($1/n$ や $1/\sqrt{n}$) の付け方に多数の選択肢が存在するが, 本サイトでは以下の形を定義式として用いる.

\[ \begin{cases} {\rm DFT:} & {\displaystyle A_k = \sum_{j=0}^{n-1} a_j\omega^{jk}}\\ {\rm IDFT:} & {\displaystyle a_j = \frac{1}{n}\sum_{k=0}^{n-1} A_k\omega^{-jk}} \end{cases} \quad \omega = \exp(-2\pi j/n) \]

目次

FFT については内容が多く,1 ページには収めきれないため,ページを分割して紹介する.

  1. 離散フーリエ変換と多数桁乗算の関係
  2. 計算量オーダーの導出
  3. 実装方式例
  4. FFT の基底
  5. 2 次元化 FFT

特殊なFFT

FFT ライブラリ

実働できる高速な FFT プログラムを書くのは大変難しい. そのため,一般的には高速に演算することができる FFT ライブラリを使用する. ここではいくつかの FFT ライブラリを紹介する.

ライブラリ 基底 基本アルゴリズム 並列計算 言語 備考
FFTW 2a・3b・5c・7d Cooley-Tukey MPI/OpenMP C 実数FFT対応
FFTSS 2a Stockham MPI/OpenMP C
FFTE 2a・3b・5c Stockham MPI/OpenMP Fortran
FFT(大浦) 2a Cooley-Tukey なし C 実数FFT対応