
We compare our implementation of SFFT to FFTW (a very efficient implementation
of the FFT algorithm) and to AAFFT (a recent
algorithm that exploits sparsity to perform a faster fourier transform).
On the graphs to the left, we fix the sparsity of the signal (the number of nonzero frequencies K) and we vary the
signal size N. On the graphs to the right, we fix the signal size N and vary the sparsity of the signal.
The graphs on the top compare SFFT 3.0 [STOC'12] (exactly k sparse algorithm) with FFTW and AAFFT. The bottom graphs compare SFFT
1.0 and 2.0 [SODA'12] to FFTW and AAFFT. You can click on each graph to enlarge. For a detailed comparison
please refer to the papers in the Publications section.

