Algorithm 991
Lee F. Richardson, William F. Eddy · ACM Transactions on Mathematical Software · 2019
We present a new algorithm for the 2D sliding window discrete Fourier transform. Our algorithm avoids repeating calculations in overlapping windows by storing them in a tree data-structure based on the ideas of the Cooley-Tukey fast Fourier transform. For an N 0 × N 1 array and n 0 × n 1 windows, our algorithm takes O ( N 0 N 1 n 0 n 1 ) operations. We provide a C implementation of our algorithm for the Radix-2 case, compare ours to existing algorithms, and show how our algorithm easily extends to higher dimensions.