I'm trying to implement a Fourier transform in an OpenGL shader. I found some literature that explains the general principles, but is a bit sparse on some details. And those details are seriously confusing me.
This paper describes the use of the Stockham FFT on the GPU. It contains the following diagram:
I understand how to calculate the discrete fourier transform for any individual point, but I'm confused how exactly the Stockham FFT proceeds. My understanding was that the FFT in general divides the input into odd and even data points, and then recursively processes these. But the diagram I added above looks reversed to me. It starts by dividing the input into the smallest segments and then adds up to larger ones, I would have expected this to work exactly the other way around.
How exactly does the divide-and-conquer part of the Stockham FFT work?