今週の離散ACMアルゴリズムに関するシンポジウムで、MITの研究者グループが新しいスパース高速フーリエ変換（ FF ）アルゴリズムを発表しました。一部の問題では、従来のFFTよりも数十または数百倍も高速です。
フーリエ変換では、初期関数が基本周波数成分（異なる周波数の調和振動）に分解されるときに係数（「振幅」）を取得します。 高速フーリエ変換を使用すると、係数のベクトルを2つのベクトルに分割し、それらのDFTを再帰的に計算し、結果を1つのFFTに結合することにより、このプロセスを高速化できます。 FFT方式は1805年にガウスによって提案され、1965年に再発見された後、現代のコンピューターの普及に広く使用されたと考えられています。 過去50年にわたって、FFTの効率を高めるために、たとえばFFTWなどの多くの試みが行われてきました。
新しいMITアルゴリズムは、FFTWよりも高速であると主張されています。 比較は科学の仕事とプロジェクトページで与えられます 。
sFFTアルゴリズム（スパース高速フーリエ変換）は、2つの既存のフィルター（ガウスフィルターとチェビシェフフィルター）に基づいて作成され、「スパース」信号でフラグメントをすばやく見つけて、それぞれの初期振幅を決定することを目的としています。 信号は、単一の振幅のスパース信号が残るまでフラグメントに分割されます（高速サンプリング）。 そしてすでにそこに、新しいアルゴリズムはそれを古典的なFFTよりも1万倍速く明らかにします。
この方法は普遍的なものではなく、現在、科学者はどの特定のアプリケーションで生産性を最大に高めるかを決定しようとしています。
MIT経由