I'm trying to understand the difference between numpy fft
and rfft
. I've read the doc, and it only says rfft
is meant for real inputs.
I've tested their performance on a large real array and found out rfft
is faster than fft
by about a third. My question is: why is rfft
fast? Thanks!
CodePudding user response:
An RFFT has half the degrees of freedom on the input, and half the number of complex outputs, compared to an FFT. Thus the FFT computation tree can be pruned to remove those adds and multiplies not needed for the non-existent inputs and/or those unnecessary since there are a lesser number of independant output values that need to be computed.
This is because an FFT of a strictly real input (e.g. all the input value imaginary components zero) produces a complex conjugate mirrored result, where each half can be trivially derived from the other half.