1
$\begingroup$

I need to be able to explain the complexity of three Fast Fourier Transform algorithms: Cooley-Tukey's, Bluestein's and Prime-factor algorithm.

Unfortunatelly, I'm a little lost in the process.


Discrete Fourier Transform general formula

\begin{align} x &= \{x_0, ... , x_{N-1}\}\\ 0 &\leq n \leq N-1 \\ X_n &= \sum^{N-1}_{k=0}x_k \cdot e^{\frac{-i\cdot 2\pi \cdot k \cdot n}{N}} \end{align}

Here's the complexity pretty clear (at least I think :-) ):

  1. We have a fixed number of multiplications and one division in the sum $\Rightarrow$ complexity of the sum content is $$O(1)$$
  2. The sum itself contains a loop from 0 to N-1, so the loop runs N-times $\Rightarrow$ the complexity of the whole sum is $$O(N) \cdot O(1) = O(N)$$
  3. And now, we have this sum for every n $\Rightarrow$ the sum will be "executed" N-times (the size of n is N) $\Rightarrow$ The complexity is $$O(N) \cdot O(N) = O (N^2)$$

Cooley-Tukey's algorithm

The point is in dividing the sum according to the Danielson-Lanczos lemma: $$ X_n = \sum^{\frac{N}{2}-1}_{k=0} x_{2n} \cdot e^{\frac{-i\cdot 2\pi \cdot k \cdot n}{\frac{N}{2}}} + e^{\frac{-i \cdot 2\pi \cdot n}{N}}\sum^{\frac{N}{2}-1}_{k=0} x_{2n+1} \cdot e^{\frac{-i\cdot 2\pi \cdot k \cdot n}{\frac{N}{2}}} $$

Every sum can be recursively divided $log_2(N)$ times:

              N
       N/2        N/2
    N/4   N/4  N/4   N/4
             ...
   1         ...        1
  1. Every sum has $O(1)$ complexity as above, so the only thing that matters is the number of iterations: $O(N), O(2\cdot \frac{N}{2}), O(4 \cdot \frac{N}{4})$... So, every step has the complexity $$O(N)$$.
  2. We have $log_2(N)$ steps, so the complexity of $X_N$ will be $$O(N \cdot log N)$$
  3. But still, this is the result just for one $X_n \Rightarrow$ Why is not the complexity multiplied by 'n' again? (as in the step 3 in the general DFT) Or is there a mistake in previous steps?

Bluestein's algorithm

The point is here in rewriting the formula to the "special" shape, where the sum is the convolution of two sequences.

enter image description here

  1. The multiplication of the sum and the exponential before it has a constant complexity $$O(1)$$
  2. Because the sum is the convolution, we can use the convolution theorem, so we must compute Fourier transforms for both sequences (which can need to be padded with zeros) and multiply them. Multiplication and zero padding are $O(1)$, Fourier transforms can be again $O(N \cdot log N)$ (we'll use Cooley-Tukey for them), so the complexity is $$ 2 \cdot O(N \cdot log N) + O(1) = O(N \cdot log N) $$
  3. And again - this is just for one $X_n$ - Why shouldn't I multiply the complexity by O(N) for every 'n'?

Prime-factor algorithm

enter image description here

And here I have simply no idea how should I compute the complexity... I'd say that two nested sums are like two loops, so $O(N^2)$, but it's obviously wrong...

$\endgroup$
  • $\begingroup$ The complexity of the algorithms becomes much easier to determine when written in pseudocode. I think your questions about an extra linear factor would be clarified by starting from scratch with a reference implementation and giving a standard analysis. $\endgroup$ – portin.daniel Mar 19 '16 at 20:11
  • $\begingroup$ @portin.daniel Ok, is there ANY way to determine it just from these mathematical formulas? I have literally zero previous experience and so I'm little anxious about making a mistake while rewriting them to presudocode :-) $\endgroup$ – Eenoku Mar 19 '16 at 20:17
  • $\begingroup$ For example, the Cooley-Tukey algorithm recursively divides a problem of size $n$ into two problems of size $n / 2$ and combines the results of solving those problems in $\Theta(n)$ time. Here, the size of the problem is the length of the input vector. If $n$ is a power of two, then $T(n) = 2T(n / 2) + \Theta(n)$ and $T(1) = \Theta(1)$ can be solved to obtain a running time of $\Theta(n \log{n})$. This is evident from the form of the algorithm, assuming the complexity of the details is easy enough to determine. $\endgroup$ – portin.daniel Mar 19 '16 at 20:48
2
$\begingroup$

The FFT complexity is usually given in terms of number of multiplications ($mul$) and additions ($add$).

General formula

That's correct $$O(N^2 \times mul + N^2 \times add)$$

Cooley-Tukey

First remember the algorithm: $$X_k = E_k + t_k O_k, k \le \frac N 2$$ $$X_k = E_{k-\frac N 2} - t_{k-\frac N 2}O_{k-\frac N 2}, k > \frac N 2$$ where $E$ is DFT of the even indexed samples, $O$ DFT of the odd indexed samples, and $t$ is the twiddle factor.

We also know that $N = 2^L,L\ge 0$

The number of operations to compute $X$ of size $N=2^L$ if $E,O,t$ are known is: $$2^{L-1} \times mul + 2^{L} \times add$$ To compute the $E$ and $O$ we need to do the computation twice but of size $2^{L-1}$ and so on. For a $i \le L$ we have to do the computation $2^{L-i}$ times.

Putting this together the total complexity is: $$\sum_{i=1}^{L}2^{L-i}O(2^{i-1} \times mul + 2^{i} \times add) = \sum_{i=1}^{L}O(2^{L-1} \times mul + 2^{L} \times add) = O(L\cdot 2^{L-1} \times mul + L \cdot 2^{L} \times add) = O(log(N)\frac N 2 \times mul + log(N)N\times add)$$

Bluestein's algorithm

Unfortunately, I'm not familiar with this algorithm

Prime-factor algorithm

$$N = N_1\cdot N_2$$ where $N_1$ and $N_2$ are relatively prime.

Notice that the algorithm is essentially DFT applied twice. The inner sum is DFT of size $N_1$ that has to be calculated for each $n_2$ (i.e. $N_2$ times). The outer sum is DFT of size $N_2$ calculated $N_1$ times. The complexity thus is:

$$O(N_2\cdot O(DFT_{N_1}) + N_1 \cdot O(DFT_{N_2})) = O(N_2\cdot N_1^2\times (mul + add) + N_1 \cdot N_2^2\times (mul + add)) = O(N\cdot (N_1+N_2)\times (mul + add)) $$

For trivial factorization $N_1=N,N_2=1$, the complexity is $O(N^2)$, but for $N_1$ and $N_2$ of similar size, this is close to $O(N \sqrt N)$.

$\endgroup$

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.