高速フーリエ変換

よみ方

こうそくふーりえへんかん

英　語

fast Fourier transform

説　明

クーリー（J.W. Cooley）とチューキー（J.W. Tukey）によって1965年によって見いだされた、有限区間の離散フーリエ変換を計算機を用いて高速に行う算法のこと。有限区間に等間隔に $N$ 個の点を考え、そこでの関数の値が $f_k$ （ $k=1, 2, \cdots, N$ ）で与えられているとき、離散フーリエ変換は
$\hat{f}_j \equiv \sum_{k=1}^N f_k\exp(-2\pi i j k /N)$ （ $j=1,2,\cdots, N$ ）
で与えられる（ $i$ は虚数単位）。容易にわかるように、単純にこれを得るために必要な計算量は $N^2$ に比例するが、高速フーリエ変換は、 $N$ が2のべき乗で表されるとき、 $N \log_2 N$ に比例する計算量で求めることができる算法である。