0
$\begingroup$

I find quite a lot of information about radix-2, radix-4, split-radix, mixed-radix FFT. There are some mentions here and there that choosing a "base case" for the recursion that is larger than the length-2 FFT (in radix-2), or length-4, etc, can help performance quite a bit. But I have a hard time finding documentation / guidelines about what kind of base case can / should be used, how the corresponding FFT should be formulated, etc. Any advices on this?

$\endgroup$
3
  • $\begingroup$ Can you provide a source or reference for your quote.? What exactly is the "base case" of an FFT ? $\endgroup$
    – Hilmar
    Nov 15, 2021 at 21:06
  • $\begingroup$ The FFT algorithms like e.g. radix-2 are often formulated as recursive algorithms, so in this context the base case is the case where the recursion ends. $\endgroup$
    – Zorglub29
    Nov 21, 2021 at 18:06
  • $\begingroup$ I see. You can certainly formulate it recursively but practical implementations rarely do. It's less efficient than iterating through the stages. $\endgroup$
    – Hilmar
    Nov 22, 2021 at 18:04

1 Answer 1

1
$\begingroup$

This FFTW paper explains it a bit.

Screenshot from the above link

More details can be found in reference 2 in the linked paper.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks, will look into it. Btw, this is again an example of this 'writing between the lines' that the base case is 'in theory' for FFT length of size 1, feels like the 'in theory' may suggest that in practice some other base case should be preferred. $\endgroup$
    – Zorglub29
    Nov 16, 2021 at 6:38
  • 1
    $\begingroup$ @Zorglub29 Have a look at the second link above. I think the answer is (as always) "it depends": it depends on the data types, it depends on the processor used, etc. etc. :-) $\endgroup$
    – Peter K.
    Nov 16, 2021 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.