レーダーのFFTアルゴリズム

レーダーのアルゴリズムとは、MITのリンカーン研究所のチャールズ・M・レーダーにより考案された高速フーリエ変換のアルゴリズムである。このアルゴリズムではサイズが素数の離散フーリエ変換（DFT）を巡回畳み込みに置き換えることで計算コストを減らす（Bluestein のアルゴリズムもまたDFTを巡回畳み込みと置き換えるアルゴリズムである)。 レーダーのアルゴリズムはDFTカーネルの周期性のみを利用しているので、このアルゴリズムは同様の特徴をもつ（素数サイズの） やに対しても適用することができる。 このアルゴリズムはデータの並び変えを少し変更し、実数データに対して更なる高速化が可能である。また、実数データについてに対する別の最適化として、 によって示された離散ハートレイ変換を用いたアルゴリズムがある。 ウィノグラードはレーダーのアルゴリズムを拡張し、素数の冪乗のサイズのDFTに適用できるアルゴリズムを考案した