Does the 'FFTW' have a cost of $kN\log_2(N)$?

Question

@Michael C. Grant wrote that "the cost of FFTW isn't an easy formula based on log_2 anymore."

But the Wikipedia article says that the FFTW (Fastest Fourier Transform in the West) "can compute transforms of real and complex-valued arrays of arbitrary size and dimension in $O(n \log n)$ time."

So can it compute $1$ forward FFT with the size $1920*1080$? in $$k*N*\log(N)/\log(2) = 5*1920*1080*\log(1920*1080)/\log(2)= 217559066$$ real operations?

Or should I perphaps take a different value for $k$?

It's often hard to tell what the implicit constant multiplying $n\log,n$ would be; the performance of prime factor FFT methods depends on the factorization of your array's dimensions. — J. M. ain't a mathematician, Jun 02 '13 at 12:46
Since $1920$ and $1080$ only have prime divisors $2$, $3$ and $5$ FFTW should perform very well in these dimensions without any (implicit) padding. — WimC, Jun 02 '13 at 13:00
@WimC: Because I am confused. So much contradicting information! — user8005, Jun 02 '13 at 13:05

score 1 · Answer 1 · answered Jun 02 '13 at 12:52

FFTW is, as I understand, a rather complex program. If you want more detail than "$O(n \log n)$", then your best recourse would be to contact the people who actually write and implement FFTW.

And keep in mind that for high performance computing, there are other things just as (and often moreso) important as the "number of real operations". FFTW is presumably designed to minimize the actual time it takes to perform the computation (and probably some concern regarding numerical precision and accuracy), rather than the number of real operations done.

Does the 'FFTW' have a cost of $k*N*\log_2(N)$?

1 Answers1

Does the 'FFTW' have a cost of $kN\log_2(N)$?