New MIT algorithm accelerates fast Fourier transform tenfold

This week at the symposium on ACM discrete algorithms, a group of researchers from MIT presented a new algorithm for the fast Fourier transform sFFT (Sparse Fast Fourier Transform), which in some tasks may be tens or hundreds of times faster than the classic FFT.

The Fourier transform involves obtaining coefficients (“amplitudes”) by decomposing the original function into elementary components — harmonic oscillations with different frequencies. The fast Fourier transform allows us to speed up this process by dividing the coefficient vector into two vectors, recursively calculating the DFT for them, and combining the results into one FFT. It is believed that the FFT method was proposed in 1805 by Gauss and rediscovered in 1965, after which it was widely used with the spread of modern computers. In the past 50 years, many attempts have been made to improve the efficiency of FFT, for example, FFTW .

The new MIT algorithm, as stated, is faster than FFTW. The comparison is given in scientific work , as well as on the project page .
')
The sFFT (Sparse Fast Fourier Transform) algorithm is based on two existing filters (Gaussian filter and Chebyshev filter) and aims to quickly find fragments with a “sparse” signal (sparse signal) and determine the initial amplitude in each of them. The signal is divided into fragments (rapid sampling) until a sparse signal with a single amplitude remains. And already there is a new algorithm that reveals it 10 thousand times faster than the classic FFT.

This method is not universal, and now scientists are trying to determine in which particular applications it will give the greatest increase in performance.

via MIT