0
$\begingroup$

@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 "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 kNlog(N)/log(2) =

5*1920*1080*log(1920*1080)/log(2)= 217559066 real operations?

Or should I perphaps take a different value for k?

|improve this question
$\endgroup$
2
$\begingroup$

You are trying to describe a complex phenomenon with a simple formula. That gets you only a rough approximation or an estimate but depending how much accuracy you need, you will have to dive deeper into the specifics. A few points

  1. Any actual operation count will depend heavily on the hardware: Instruction set, pipeline, memory architecture, cache strategies, hardware accelerators, etc. In many cases the choice of the "best" algorithm is actually hardware dependent. Your best shot here is benchmarking and profiling on the target hardware.
  2. The good old N/2*log2(N) formula basically describes the "number of butterfly operation" in a standard Cooley Tuckey FFT. So a 32-point FFT has 16*5 = 80 butterfly operations. There are 5 stages of 16 butterflies each. This is typically (but not always) the bulk of the work so it's a decent estimate for the overall complexity.
  3. One butterfly has one complex multiply and two complex adds (or on add and one subtract if you are picky about). The number of operations required will depend widely on the Hardware. An Analog Devices Sharc SIMD processor can do this with about 3 operations, an general purpose processor might take up to 20 operations.
  4. There is a lot of other stuff that isn't part of the butterflies: bit-reversing, looping & branching, coefficient calculation storage and retrieval. These can factor heavily into your MIPS count as well and are even more hardware dependent.
  5. The first two stages (for decimation in time) use only simple coefficients like +1, -1, +j, -j and don't need a full complex multiply. Most algorithms take advantage of this and so the first 2*log2(N) butterflies are a little cheaper. By how much depends again on the hardware.
  6. Non power of two FFTs get more complicated. Let's look at a 96 point FFT. First you need 3 FFTs of 32 points each, so that is 3*5*16 = 240 butterflies. Then you need to assemble the result which takes 2 complex multiplies and 2 complex adds per sample, so it's another 96*2=192 extra complex multiplies and 192 complex adds. Total would be 432 mpy and 672 adds. A 128 FFT would have 448 mpy and 896 adds, so it may be better just to zero pad and use the larger power-of-two FFT as it greatly simplifies coefficient calculation and storage.
  7. The more prime factors you have in the FFT length the more complicated and less efficient the algorithm gets.
  8. In your specific case, I'd zero pad the 1920 to 2048 (unless you need true circular convolution, which I don't believe you do here). It's highly unlikely that any prime factorization (128*3*5) would do better. The 1080 is awkward, since it's just a tad over 1024. I'd probably zero pad to 1280 and do a 256*5 or zero pad to 1152 and do 128*9. You can also try the 8*27*5 and see if that's better.
|improve this answer
$\endgroup$
  • $\begingroup$ Why zeropadding? 1920=$2^7*3*5$ and 1080=$2^3*3^3*5$ But if you need to give a k-value. Would it be something else than 5? $\endgroup$ – user8005 Jun 2 '13 at 13:07
  • $\begingroup$ @user8005: What Hilmar is saying is that it's possible that you could get faster performance by zero-padding to a pure factor-of-2 size. While it has good algorithms for a bunch of small prime factors, power-of-2 sizes still typically are fastest. FFTW uses a lot of different algorithms under the hood that it chooses from at runtime, so the best policy is just to benchmark each case and pick what works best on your target platform. $\endgroup$ – Jason R Jun 2 '13 at 13:10
  • $\begingroup$ @user8005: depends on what you mean by "k". If you want to estimate "processor cycles per FFT" than this is heavily hardware dependent. If you want scalar operations, 5 is rough approximation. The actual count is a much more complicated formula $\endgroup$ – Hilmar Jun 2 '13 at 13:52
  • $\begingroup$ I meant scalar operations. The actual count is a much more complicated formula? The actual count of scalar operations? Why is it more complicated ? $\endgroup$ – user8005 Jun 2 '13 at 13:57
  • $\begingroup$ "Why is it more complicated ?" See point 4. and 5. in Hilmar's answer. $\endgroup$ – pichenettes Jun 2 '13 at 15:03
1
$\begingroup$

You're confusing two somewhat related but different concepts: cost and complexity.

  • Cost is a way of expressing the total number of computations to perform a particular transform. For the Cooley-Tukey FFT, this is often quoted as $5N \log N$ scalar operations (real multiplies and additions). This is a pretty straightforward idea.

  • Complexity (using big-O notation) refers to how the algorithm scales asymptotically as you increase the transform length $N$. It doesn't attempt to give an exact operation count for any particular transform size; it just can be used to compare two different implementations of an algorithm to see how they will scale for larger datasets.

    Example: Consider an algorithm that is $O(N \log N)$. Consider two different transform lengths: $N_1 = 2^{16}$ and $N_2 = 2^{24}$. Using the known complexity of the algorithm, we can estimate how the costs for the two transform lengths relate:

    $$ \frac{\text{cost}(N_2)}{\text{cost}(N_1)} \approx \frac{N_2 \log N_2}{N_1 \log N_1} = \frac{N_2}{N_1} \log(N_2 - N_1) $$

    Again, this doesn't tell us the exact cost for either transform length; instead, it just gives us a feel for approximately how much more costly it would be as one increases the algorithm's working set.

|improve this answer
$\endgroup$
  • $\begingroup$ So, what is the cost of the FFTW in this case (1920*1080)? $\endgroup$ – user8005 Jun 2 '13 at 13:41
  • $\begingroup$ As far as I know, it is not defined by the authors of FFTW. It would be dependent upon the exact algorithm that it chooses for your case, which is going to be platform dependent. It will also be dependent upon all of the hard-to-predict issues that Hilmar pointed out in his answer. $\endgroup$ – Jason R Jun 2 '13 at 13:51
  • $\begingroup$ So, any reasons to believe the k (scalar operations) is not 5? $\endgroup$ – user8005 Jun 2 '13 at 13:59
  • $\begingroup$ Yes, there is. You don't know what algorithm it's using internally, so you have no reason to believe that it is 5. $\endgroup$ – Jason R Jun 2 '13 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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