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 ページには収めきれないため、ページを分割して紹介する。
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対応。コンパイルに非常に時間がかかる。 |