Implementation of the 2D Tree Radix-2 Sliding Window Discrete Fourier Transform. The algorithm paper will appear in the 45th volume of ACM TOMS (https://toms.acm.org/), and the software package will be in the Collected Algorithms of the ACM (http://calgo.acm.org/). 

In addition to the algorithm, we provide a driver program that runs the algorithm on a 2D array, a program that proves numerical stability, and a program that times our algorithm against taking a 2D DFT (SWDFT) or 2D FFT (SWFFT) for each window position.

Files corresponding to the 2D Tree SWDFT algorithm in the src/ directory. 
tswdft2d.c		--- C function that implements our algorithm.
tswdft2d.h  	--- Constants, macros, and functions used by our algorithm. 
driver2d.c		--- Driver program that runs our algorithm on a randomly generated 2D array
utils.c 		--- Utility functions used by our algorithm
Makefile 		--- Compiles the driver program 

Files for checking correctness and timing our algorithm are in the tests/ directory:
swdft2d.c  		--- Implementation of the 2D Sliding Window discrete Fourier transform (SWDFT)
swfft2d.c 		--- Implementation of the 2D Sliding Window Fast Fourier transform (SWFFT)
stability.c		--- Verifies that our algorithm and the 2D SWFFT give identical answers. 
timing.c		--- Times our algorithm against the 2D SWDFT and 2D SWFFT. (Note: Taking 
					the 2D SWDFT for large arrays and window sizes is very computationally intensive.)
Makefile		--- Compiles the stability and timing programs 

Both makefiles use the gcc compiler, following the gnu99 standard.

--- Running the Driver, Stability, and Timing Programs ---
Compile and run the driver2d program with the following commands:

cd src
make 
./driver2d

Similarly, compile and run the timing and stability programs with:

cd tests
make 
./timing
./stability

You can manually change the window and array sizes in these executables.