0
$\begingroup$

According to my understanding the FFT operation for a vector whose length is $N$ has a complexity of $ \frac{N}{2}\log_{2}{N}$ complex multiplication and $ N\log_{2}{N}$ complex addition. I was wondering if I performed that FFT operation using another way, will that have the same complexity too?

For example, let have the FFT matrix whose size is $ N \times N $ and the vector $x$ also $N \times 1$, so I will first spread each value in the vector $x_i$ with the column $F_i$ taken from the FFT matrix, I will have $N$ vectors in that case with the length of each one of $N$, I will then sum all them up to have the same result of FFT operation mentioned above. So, will the complexity in that case will be the same of that mentioned above? Or it will be changed?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let's straighten out the terminology first: the FFT is a specific algorithm to implement a mathematical operation, namely the Discrete Fourier Transform or DFT for short.

There a multiple ways to implement the DFT and the FFT is one of them. The FFT is efficient if the length of the DFT an be factored into small-ish primes. It's most efficient if the length is a power of 2 and in this case it has indeed a complexity of $N\log_2(N)$. For other lengths that's not the case.

You can certainly implement a DFT also by matrix multiplication or direct evaluation of the defining equation but than it's not an FFT anymore since it's a different algorithm. Also for these examples the complexity will be $N^2$.

For larger $N$ (which are can be suitably prime factored) the difference is substantial and hence the FFT is the most popular way to implement the DFT.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Yes, I agree with you, but I mean can we use also the algorithm of FFT with my above mentioned method to get the same complexity of FFT? $\endgroup$
    – Sajjad
    Mar 3 at 7:10
  • $\begingroup$ @Sajjad that makes no sense-what you describe is specifically not doing the FFT. It's kind of the opposite. $\endgroup$
    – Marcus Müller
    Mar 3 at 8:44
  • $\begingroup$ @MarcusMüller I think it does make sense as by using my above way, the spreading the first element with first column of dft matrix requires only one multiplication and one addition as all the elements of first column are the same, and so on for other columns where some similarity should exist. $\endgroup$
    – Sajjad
    Mar 3 at 13:19
  • $\begingroup$ but it's not an FFT when you do that. End of story! And you can count the multiplications yourself: it's the same number of multiplications as in a naive DFT matrix multiplication. You are indeed making the memory access pattern on the coefficients you multiply with a bit better, at the expense of having much more than you need (if you were using an FFT), and having a much worse memory access pattern for your input data. $\endgroup$
    – Marcus Müller
    Mar 3 at 13:20
  • $\begingroup$ @MarcusMüller totally agree with you that is not FFT, and also that FFT is the straightforward solution for that. However, I need to use that way for developing other things. So, why do you think I will have the same multiplications of naive DFT matrix; I have taken an example in my previous commenr thst first column will be 1 multiplication instead of N when using naive DFT matrix, and so on. $\endgroup$
    – Sajjad
    Mar 3 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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