These are the supporting examples for the paper "Generating and Searching Families of FFT Algorithms." You will need to install Python (www.python.org) and SciPy (www.scipy.org) to execute these examples. They have been tested under Linux, but should work on Windows and Mac OS X platforms. To execute an example:

python sz256_6664.py

You should see a report similar to:

N		= 256
FLOPS	= 6664
MAE   	= 2.53781370918e-14

N is the size of the FFT. FLOPS is the the FLOP count. MAE is the mean absolute error when all output values of this FFT are compared to a the SciPy "golden" FFT. The MAE should be a very small number. The initial input operands for the FFT are random and consequently the MAE will be different for every execution of the script.

There are five example FFTs included:

sz256_6664.py	Traditional size-256 split-radix requiring 6664 FLOPs.
sz256_6616.py	New size-256 FFT requiring 6616 FLOPs with all twiddle factors modulus 1.
sz512_15128.py	New size-512 FFT requiring 15128 FLOPs with all twiddle factors modulus 1.
sz32_restrictedtfs.py	New size-32 FFT with limited set of twiddle factors. See file for explanation.
sz64_restrictedtfs.py 	New size-64 FFT with limited set of twiddle factors. See file for explanation.

All FFTs are inplace and executed by repeated calls of size-2 butterflies with different twiddle factors. All FFTs are flat and unrolled. These FFTs are not general algorithms but meant for illustration and clarity. See the file TestFFT.py for details regarding the Butterfly (BF) method.

The file TestFFT.py contains code that executes the FFTs via the size-2 butterfly calls. It does the following:

* Creates initial random complex data for the FFT
* Computes size-2 butterflies and stores the result in place.
* Tallies all floating point operations. 
* Compares the final concrete result with a result from SciPy and reports the mean absolute error.
* Performs symbolic checks of the graph structure and computations.

TestFFT.py is a script and is best understood by reading it. It is instructive to copy one of the five example FFTs and randomly change some of the twiddle factors to see how errors are detected and FLOP counts change.

The subdirectories smt and cnf contain SMT and SAT models, respectively, for the sz256_6616, sz512_15128 and sz64_restrictedtfs examples. The larger FFTs are partitioned, with the partition number _* appended to the name.

The subdirectory smt2.0 contains SMT 2.0 QF_BV and QF_LIA benchmarks.

Please e-mail any questions to: steve@softerhardware.com.



