FFT as Nested Multiplication, with a Twist
Carl de Boor · SIAM Journal on Scientific and Statistical Computing · 1980
A simple, yet complete and detailed description of the fast Fourier transform for general N is given with the aim of making the underlying idea quite apparent. To help with this didactic goal, a simple twist, i.e., a shifting of information from rows to columns during the calculations, is introduced which allows us to give a simple meaning to intermediate results and assures that the final results need no further reordering.