I'm not really sure, if this is the right place to ask this question. I would have asked on stackoverflow, but since my question is rather theoretical, I ask here. When I'm wrong, please migrate. Thank you :)I'm trying to multiply polynomials using FFT. When doing an FFT in-place, the output is in bit-reverse order, which doesn't matter much, because when doing a convolution and an inverse FFT, the order will be reversed again.I'm now trying to reduce memory bandwith using Bailey's 4-step FFT. While a normal FFT reads the data as often as $k$ times when the size of the transform is $2^k$, the 4-step FFT does it only two times (not counting CPU cache access). I'm implementing it as follows:Write my data as an $n_1 \times n_2$ matrix. Do $n_2$ in-place FFTs on the columns. Reorder the columns.Do the multiplication with the roots of unity (see paper)Do $n_1$ in-place FFTs on the rows, do not re-order the data, because it's not needed for the convolution to work.However, when I omit the reordering in step 1, I'll get incorrect results.  The re-ordering requires significant additional resources. Is it possible to get rid of it?
Baileys 4-step FFT without bit reverse sorting
algorithms