0
$\begingroup$

I read several explanations about why the FFT algorithm has the complexity $\mathcal{O}(n \cdot \log(n))$ and not just $\mathcal{O}(n^2)$ like if we directly multiplied the input by the Vandermonde Matrix, but I think I am missing something. I understand that we recursively split the problem in two parts, with the odd elements on one side and the even elements on the other side as shown here:

\begin{align} X_k &= \sum_{n=0}^{N-1} x_n \cdot e^{-i~2\pi~k~n~/~N} \\ &= \sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i~2\pi~k~(2m)~/~N} + \sum_{m=0}^{N/2 - 1} x_{2m + 1} \cdot e^{-i~2\pi~k~(2m + 1)~/~N} \\ &= \sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i~2\pi~k~m~/~(N/2)} + e^{-i~2\pi~k~/~N} \sum_{m=0}^{N/2 - 1} x_{2m + 1} \cdot e^{-i~2\pi~k~m~/~(N/2)} \end{align}

But I don't see why there are less operations when we split it in two. As I understand it, for each $X_k$ we still have to do $N/2$ additions and multiplications for the even part and $N/2$ additions and multiplications for the odd part, which is exactly the same as if we directly did N additions and multiplication for each $X_k$. So, why are there less operations needed using the FFT?

$\endgroup$
4
  • 1
    $\begingroup$ Have you actually worked through an example and seen what happens? That teaches you way more than just staring at formulas. $\endgroup$
    – Arthur
    Jan 6, 2021 at 14:01
  • $\begingroup$ Yes I tried with a 4x4 matrix, but I didn't see a change in the number of operations between multiplying a 4x4 matrix with an input of length 4 or multiplying twice a 2x4 matrix with an input of length 2. But If you can find a good exemple that might help me. $\endgroup$ Jan 6, 2021 at 14:26
  • 2
    $\begingroup$ The point of FFT is that it is recursive. Once you split in two, you take each part and split those in two too. And so on as far down as it goes. This will reduce the number of total multiplications and additions to $O(n\ln n)$ if done correctly. $\endgroup$
    – Arthur
    Jan 6, 2021 at 14:32
  • $\begingroup$ Yes but my question is why splitting it in two reduces the number of operations. Otherwise it is clear for me that if it reduces the number of operations each time you split the problem in two, then you get a complexity of order $n \cdot log(n)$ $\endgroup$ Jan 6, 2021 at 14:36

2 Answers 2

2
$\begingroup$

Consider, for instance, that you have a degree-7 polynomial $f$, and you want to evaluate it at every 8th root of unity (primitive and non-primitive).

Naively, this takes 28 multiplications and 7 additions per evaluation, for a total of 308 operations.

However, we can do much better. Split $f$ into a sum $$ f(x)=g_e(x^2)+xg_o(x^2) $$ for two degree-3 polynomials $g_e$ and $g_o$. Now if we can evaluate $g_e(x^2)$ and $xg_o(x^2)$ for only the first four $8$th roots (1, as well as the ones with positive imaginary part), then because of the even-ness / odd-ness of the two functions, evaluating $f$ at the remaining four roots come basically for free.

In total (including the squaring $x^2$), with naive polynomial evaluation, this gives 15 multiplications and 7 additions for each of the first four roots, and just a single subtraction for each of the other four. A total of 76 operations rather than 308. However, we aren't done with the optimisations.

Now for the really cool part: evaluating $g_e(x^2)$ and $g_o(x^2)$ for the first four eighth roots beginners evaluating $g_e(x)$ and $g_o(x)$ for all the fourth roots of unity. So exactly the same trick can be applied again! So it turns out that the above paragraph is very pessimistic; it takes much less than 15 multiplications and 7 additions for each of the first four eighth roots.

Even if you, from the start, are clever about how you evaluate $f$ by, say, using your calculated $x^4$ when you find $x^5$ (the reduction from 28+7 to 15+7 operations is of this nature), the savings are considerable, as each step of recursion essentially halves the number of points you need to evaluate (more than a subtraction) at.

Consider, for instance, how this method would calculate its last point, $f(e^{7\pi i/4})$. It would be found as $g_e(e^{14\pi i/4})+e^{7\pi i/4}g_o(e^{14\pi i/2})$. However, we have $e^{14\pi i/4}=e^{6\pi i/4}$, which means that because we previously calculated $$f(e^{3\pi i/4}) = g_e(e^{6\pi i/4}) + e^{3\pi i/4}g_o(e^{6 \pi i/4})$$ we got almost everything we need, and get $$f(e^{7\pi i/4}) = g_e(e^{6\pi i/4}) - e^{3\pi i/4}g_o(e^{6 \pi i/4})$$This is what I mean by $f(e^{7\pi i/4})$ costing only a single subtraction.

$\endgroup$
5
  • $\begingroup$ Thanks for the exemple. So I'm I right to say that the operations that we avoid to do in this algorithm are just the computations of the powers of x? Couldn't we just avoid that by precomputing the Vandermonde matrix? By doing so, it would just take 8 multiplications and 7 additions per evaluation right? And this would still be in the order of $O(n^2)$ since we have N evaluations to do... $\endgroup$ Jan 6, 2021 at 15:43
  • $\begingroup$ @NicolasSchmid No, the powers of $x$ is not where FFT gets its strength. That's just something that comes along for the ride without having to think too much about it. It gets its strength for calculating half the points for the cost of a single subtraction each (regardless of the degree of $f$). Then recursing, getting half the remaining points for two subtractions and an addition each. And so on. Basically, only a single full independent polynomial evaluation of $f$ is done. All the others are gotten by adding and subtracting the different odd and even parts at different recursion levels. $\endgroup$
    – Arthur
    Jan 6, 2021 at 15:57
  • $\begingroup$ The number of subtractions per "for free" point doubles for each recursion (and the number of additions is one less than that), so for many points it averages out to about two subtractions and one addition per evaluation point, in addition to calculating $f(1)$ and storing strategic intermediate values of that calculation. $\endgroup$
    – Arthur
    Jan 6, 2021 at 16:09
  • $\begingroup$ Ok I think I got it. We have less operations because when $k > N/2$ we don't have to compute the sum again because the two sums give the same result because of the $N/2$ periodicity of $\sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i~2\pi~k~m~/~(N/2)}$. I did not really understand what you mean with substractions, I only see additions and multiplications, but thank you anyway. $\endgroup$ Jan 6, 2021 at 16:51
  • $\begingroup$ @NicolasSchmid There is a difference between the taught formulas and the intuitive reasoning behind them. The formulas treat each point rather uniformly. My explanation here doesn't. See my edit for an example of what I mean. $\endgroup$
    – Arthur
    Jan 6, 2021 at 20:18
1
$\begingroup$

You are missing the most important ingredient of FFT, which is the reuse of redundant terms. From your given equation, $$ X_k = \sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i~2\pi~k~m~/~(N/2)} + e^{-i~2\pi~k~/~N} \sum_{m=0}^{N/2 - 1} x_{2m + 1} \cdot e^{-i~2\pi~k~m~/~(N/2)} $$ we change index $k\to k + N/2$ $$ \begin{align} X_{k+N/2} &= \sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i~2\pi~(k+N/2)~m~/~(N/2)} \\ & + e^{-i~2\pi~(k+N/2)~/~N} \sum_{m=0}^{N/2 - 1} x_{2m + 1} \cdot e^{-i~2\pi~(k+N/2)~m~/~(N/2)} \end{align} $$ Here, we can expand $$ \begin{align} e^{-i~2\pi~(k+N/2)~m~/~(N/2)}&=e^{-i~2\pi~k~m~/~(N/2)}e^{-i~2\pi~(N/2)~m~/~(N/2)} \\ &=e^{-i~2\pi~k~m~/~(N/2)}e^{-i~2\pi~m~} \\ &=e^{-i~2\pi~k~m~/~(N/2)} \end{align} $$ and $$ \begin{align} e^{-i~2\pi~(k+N/2)~/~N} &= e^{-i~2\pi~k~/~N}e^{-i~2\pi~(N/2)~/~N} \\ &= e^{-i~2\pi~k~/~N}e^{-i~\pi} \\ &= -e^{-i~2\pi~k~/~N} \end{align} $$ With the two above, we can now rewrite $X_{k+N/2}$ as $$ X_{k+N/2} = \sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i~2\pi~k~m~/~(N/2)} - e^{-i~2\pi~k~/~N} \sum_{m=0}^{N/2 - 1} x_{2m + 1} \cdot e^{-i~2\pi~k~m~/~(N/2)} $$ having exactly the same terms as $X_k$ barring the difference of using subtraction instead of addition. Now, instead of calculating for each $k={0\dots N-1}$ we only need to calculate for $k={0\dots N/2-1}$, effectively halving the arithmetic operations required.

$\endgroup$
1
  • $\begingroup$ Thanks this is indeed a better answer than the previous one $\endgroup$ 17 hours ago

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .