The Gopher Fast Fourier Transform (GFFT) is an implementation of the frequency
sparse FFT algorithm described in "Combinatorial Sublinear-Time Fourier Algorithms"
by M.A. Iwen (http://www.math.duke.edu/~markiwen/DukePage/Papers/JcFFTsubmit.pdf).
This package includes GFFT in several variants, code for benchmarking them, and
slightly modified versions of the Ann Arbor Fast Fourier Transform (AAFFT) used
for benchmarking in "Signal Approximation via the Gopher Fast Fourier Transform"
by I. Ben Segal and M.A. Iwen (http://www.ima.umn.edu/preprints/jul2010/2326.pdf)
and another forthcoming paper.
The FFTW 3 library is necessary to compile the included code, which can be obtained
at http://www.fftw.org/ free of charge.
Two slightly different versions of both GFFT and AAFFT are included, one designed
to benchmark the implementations given a signal of known sparsity, the other designed
to benchmark the robustness of the algorithms to incorrect sparsity specifications.
The command line parameters for the latter versions of GFFT differ from the former only in
that the sparsity to be assumed by the algorithms is included as an additional parameter
after the actual sparsity of the generated test signals. With this in mind I will only give
the syntax for the former versions for GFFT.
Their are four variants of GFFT included here. GFFT-Fast-Det (implemented in gfftsubdet.cpp) is
deterministic and runs in sublinear time. GFFT-Fast-Rand (implemented in gfftsubrand.cpp) is a
non-deterministic monte-carlo extension of GFFT-Fast-Det. GFFT-Slow-Det (implemented in
gfftsuperdet.cpp) is deterministic and runs in superlinear time with less samples. GFFT-Slow-Rand
(implemented in gfftsuperrand.cpp) is a non-deterministic monte-carlo extension of GFFT-Slow-Det.
More details about these variants can be found in the papers referenced above.
To compile the GFFT benchmarking program with GCC, enter the command:
g++ -O3 -lfftw3 fftw.cpp gfftsubdet.cpp gfftsubrand.cpp gfftsuperdet.cpp gfftsuperrand.cpp benchmark.cpp -o benchmark.o
Then the benchmarks can be run with the following command:
./benchmark.o <test signal size> <test signal sparsity> <number of test signals> <parameter controlling accuracy of monte-carlo algorithms> <file in which to store test signals>
The optimal monte-carlo parameter depends upon the signal size and sparsity and can be found through experimentation,
but will generally be in the range 0.5-2.0.
To compile the AAFFT benchmarking program for signals of known sparsity with GCC, enter the command:
g++ Demo_Fixed_K.cc -O3 -lfftw3 -o Demo_Fixed_K.o
or:
g++ Demo_Fixed_N.cc -O3 -lfftw3 -o Demo_Fixed_N.o
the difference being that the first can be used to test signals of varying size with fixed sparsity,
while the second can be used to test signals of varying sparsity for fixed size.
The syntax is then:
./Demo_Fixed_<K/N>.o <test signal sparsity/size> <number of test signals> <file containing test signals generated by GFFT benchmarking>
To compile the AAFFT benchmarking program for signals of approximated sparsity with GCC, enter the command:
g++ Demo.cc -03 -lfftw3 -o Demo.o
The syntax is then:
./Demo.o <test signal true sparsity> <test signal sparsity approximation> <number of test signals> <file containing test signals generated by GFFT benchmarking>
The data collected during benchmarking is saved in saveral files as documented in benchmarking.cpp for GFFT and
Demo_Fixed_<K/N>.cc and Demo.cc for AAFFT. A future version of this file will include such documentation as well.
Please email me at sega0052@umn.edu with any questions about GFFT.
GFFT and AAFFT are distributed under the MIT License.
