円周率.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)$ の計算量で結果を得られることが知られている。 これを利用することで多倍長の乗算を $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 i/n) \]

目次

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

  1. FFT と多倍長乗算の関係
  2. 計算量オーダーの導出
  3. 実装方式例
  4. FFT の基底
  5. 多次元化 FFT

特殊なFFT

FFT ライブラリ

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

ライブラリ 基底 基本アルゴリズム 並列計算 言語 備考
FFTW $2^a\cdot3^b\cdot5^c\cdot7^d$ Cooley-Tukey MPI/OpenMP C 実数FFT対応
FFTE $2^a\cdot3^b\cdot5^c$ Stockham MPI/OpenMP Fortran
FFT(大浦) $2^a$ Cooley-Tukey なし C 実数FFT対応
OTFFT $2^a$ Stockham OpenMP C++ 実数FFT対応。コンパイルに非常に時間がかかる。