高速フーリエ変換
よみ方
こうそくふーりえへんかん
英 語
fast Fourier transform
説 明
クーリー(J.W. Cooley)とチューキー(J.W. Tukey)によって1965年によって見いだされた、有限区間の離散フーリエ変換を計算機を用いて高速に行う算法のこと。有限区間に等間隔にN個の点を考え、そこでの関数の値がfk(k=1, 2, …, N)で与えられているとき、離散フーリエ変換は
$$ \hat{f}_j \equiv \sum_{k=1}^N f_k\exp(-2\pi i j k /N)\quad(j=1,2,\cdots, N)$$
で与えられる(iは虚数単位)。容易にわかるように、単純にこれを得るために必要な計算量はN2に比例するが、高速フーリエ変換は、Nが2のべき乗で表されるとき、N log2 Nに比例する計算量で求めることができる算法である。
2023年05月13日更新
この用語の改善に向けてご意見をお寄せください。
受信確認メール以外、個別のお返事は原則いたしませんのでご了解ください。