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 non-zero 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.