0
$\begingroup$

What is the RFFT and iRFFT complexity for 1D and 2D?

Here is some starting point.

1D RFFT

  • The FFT is $\mathcal{O}(N\log N)$
  • RFFT computes $N//2 + 1$ frequencies instead of $N$.
    • Thus, RFFT is $\mathcal{O}([N//2 + 1]\log N)$ = $\mathcal{O}\left (\frac{N}{2}\log N \right )$
  • Question: What about iRFFT? Is it $\mathcal{O}(N\log N)$ or $\mathcal{O}\left (\frac{N}{2}\log N \right )$ ?

2D RFFT

  • The 2D-FFT is $\mathcal{O}(2N^2\log N)$
  • RFFT computes $(N//2 + 1)N$ frequencies instead of $N^2$.
    • Thus, RFFT is $\mathcal{O}([N//2 + 1]N\log N + N^2 \log N)$ = $\mathcal{O}\left (\left [ \frac{3}{2} N + 1\right ] N \log N \right )$ = $\mathcal{O}\left (\frac{3}{2} N^2 \log N \right )$
  • Question: What about iRFFT? Is it $\mathcal{O}(2N^2\log N)$ or $\mathcal{O}\left (\frac{3}{2} N^2 \log N \right )$?

Am I getting anything wrong?

$\endgroup$
3
$\begingroup$

In Big-O notation, $\mathcal{O}(N\log N)= \mathcal{O}(\frac N2\log N)$, as big-O notation only describes an upper bound for growth up to a constant factor, so your first question is kind of impossible to decide; in practice, the effort for a cleverly implemented real-valued FFT will be less than that of a (normal, complex) FFT.

But whether it will be exactly half might be doubted: as basically everywhere in numerical algorithm, the number of operations isn't actually sufficient to describe the effort or time needed. When I look at my PC, it does about 200 to 1000 multiplications in the time it needs to access a random address in RAM that's not cached. So, you'll see big jumps in actual time when your data size crosses cache size boundaries, which might happen later with real-valued data; or it might not matter at all.

The same problem, big-O notation only requiring the existince of a constant, finite factor $k$ such that the complexity of the algorithm stays below $k$ times the function in the parentheses, remains for your 2D question.

Generally, you'll find that the pure description through numbers of multiplications and additions makese nearly no sense, unless you're dealing with very large numbers, so that you can be asymptotically sure to never be able to e.g. align memory accesses. I wish people would teach that more intensely when they tell people about algorithmic complexities: for algorithms where the input data is almost certainly not randomly spread across memory, the memory access usually becomes a very dominant factor!

In the case of FFTs, the problem is even more prominent: Everyone (and their grandma) knows that the $N$-point FFT's complexity $c(N)$ is in $\mathcal O(N\log N)$, but nobody notices that there's quite possibly a very large constant factor in $\lvert c(N)\rvert \le k\cdot N\log N$ (and that the base of the logarithm isn't even defined), and that the formal definition especially notes that this only needs to hold true for all $N$ larger than some very large $N_0$.

But it gets worse: Practically, we know that on "normal" computers, on most FPGA IP cores and DSP slices, and most other platforms, power-of-2 FFTs are very fast, whereas FFTs with larger prime factors do still exist. But, I wouldn't be surprised at all if the $N_1=4\cdot 2^{n}$-FFT was faster than the $N_2=3\cdot 2^{n}$-FFT, even if by judging the O-notation, for sufficiently large $n$ that shouldn't be the case! People really mislead when they tell other people the FFT is always in $\mathcal(N\log N)$; you'll need to put the FFTs with the same prime factors in separate classes and only change the exponent of one of these prime factors for that to actually be a sensible statement.

Sorry that I'm such a downer about big-O notation – it's just that beyond showing how a Cooley-Tukey / Radix-2 FFT can save you computation for power-of-2 FFTs, it's very rarely used to imply anything correct, less frequently even to arrive at a useful result!

$\endgroup$
6
  • $\begingroup$ My belief is it is more a very crude estimate of resource needs. $\endgroup$ – Laurent Duval May 3 at 22:27
  • $\begingroup$ ah, you mean in intermediate coefficient storage? $\endgroup$ – Marcus Müller May 3 at 22:43
  • $\begingroup$ When I look at my PC, it does about 200 to 1000 multiplications in the time it needs to access a random address in RAM that's not cached. I wish I knew how to estimate that (searching it later). $\endgroup$ – Eduardo Reis May 4 at 9:14
  • $\begingroup$ The post is extremely helpful since it brings attention that to the average/practical user, the big-O notation is likely to be less important than hardware factors. I really appreciated it, I learned with it. But, I think my question is still open towards the RFFT. $\endgroup$ – Eduardo Reis May 4 at 9:19
  • $\begingroup$ I like this answer, but at the same time it leave me stuck - or better saying: it didn't pointed to what I was looking for specifically. Though $\mathcal{O}(n/2) = \mathcal{O}(n)$ I am still looking for differentiating between them, or scenarios differentiate the complexity between FFT, RFFT, 2D-FFT and 2D-RFFT. After all, is there a value on reducing by half the number of operations? I am very thankful for pointing that the algorithm complexity is not the only factor to be considered. If the issue is the notation, would FLOPS be a more precise notation to differ between $N$ and $N/2$? Thanks. $\endgroup$ – Eduardo Reis May 27 at 21:20
0
$\begingroup$

I am seconding Marcus Müller's excellent answer with a recent post on Quora: Why does C code run faster than Python's?

Let’s write a simple function that adds up all numbers in an array.

"It is the same algorithm, yet they have drastically different performance. I called these functions 1 million times for 1K arrays, the python version took 32 seconds with cpython and 1.032 seconds with pypy, the C version took 2.12 seconds without optimization and just 0.03s with -O2 optimization."

As you can see, even a simple addition can be accelerated by orders of magnitude by changing the language or the compilation options. This is of course even more complicated with adds, multiplies, divisions. In some cases, all those operations are considered equivalent, in others, a multiply is considered $n$-times the complixity of an add. This is even worse with operations like Multiply–accumulate operation

$$a \leftarrow a+(b\times c) $$

For the FFT, there exists a whole routine lists in FFTW tjhe "Fastest Fourier Transform in the West"

FFTW is a C subroutine library for computing the discrete Fourier transform (DFT) in one or more dimensions, of arbitrary input size, and of both real and complex data (as well as of even/odd data, i.e. the discrete cosine/sine transforms or DCT/DST). We believe that FFTW, which is free software, should become the FFT library of choice for most applications.

For a more precise result, you should consider the Big Theta $\Theta()$ notation of the Bachman-Landau family instead of the Big O $O()$. Thus you may bound $f$ $ both above and below by $\Theta() asymptotically. It is probably safer to compute separately the adds, the multiplies and the divisions.

$\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.