円周率.jp > 多数桁計算 > FFT

FFT

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

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

DFT: Ak\sum_{j=0}%5e{n-1} ajωjk,    IDFT: aj\frac{1}{n} \sum_{k=0}%5e{n-1} Akω-jk,    ω=exp(−2πi/n)

目次

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

なお,以下のページでは解説の都合上, 疑似プログラムの記載において多次元配列も使うことがある. A[d1d2d3] と書く場合,d3 が連なっている方向にメモリは連続しているものとする. つまり C# のような表記をとる.

  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対応