Home Theory Evaluation Code Applications Hardware Publications News People Workshops

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.