Evaluation :

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 (exact k sparse algorithm) with FFTW and AAFFT. The graphs below compare SFFT 1.0 and 2.0 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.

---