ABSTRACT
This chapter looks at what the FFT (more precisely: its “most classic” version) actually does. None of the hand-coded implementations will, of course, be able to outperform torch_fft_fft(), torch delegating to highly optimized C++ code. The simplifications resulting from decimation in time can be presented as a two-step logic. It makes direct use of the fact that the DFT matrix WN can be factored into three sparse matrices, each materializing one of the three stages inherent in the rule: split up the input into even and odd indices; compute the two half-sized FFTs; recombine the results. The sorting may conveniently be done using bitrevorder(), a function provided by the R package gsignal. Algorithmic properties are like Platonic ideas: pure and noble in theory, but often, hard to enliven in the lowlands of everyday life.
