20

I'm trying to write a bit of code that will predict the time taken to perform a discrete Fourier transform on a given n-dimensional array, but I'm struggling to get my head around the computational complexity of n-dimensional FFTs.

As I understand it:

  • The 1D FFT of a vector of length N should take k*(N*log(N)) where k is some timing constant

  • For an M*N matrix, the 2D FFT should take:

    N*(k*M*log(M)) + M*(k*N*log(N)) = k*M*N*(log(M)+log(N))

    since it requires taking 1D FFTs in each row and column

How does this generalize to the ND case? Does it follow that it should be k*prod(dimensions)*sum(log(dimensions))?

mtrw
  • 34,200
  • 7
  • 63
  • 71
ali_m
  • 71,714
  • 23
  • 223
  • 298

1 Answers1

21

If we take your derivation of 2D a bit further, it becomes clear:

N*(k*M*log(M)) + M*(k*N*log(N)) = k*M*N*(log(M)+log(N))

becomes:

                                = k*M*N*(log(M*N))

For N dimensions (A,B,C, etc...), the complexity is:

O( A*B*C*... * log(A*B*C*...) )

Mathematically speaking, an N-Dimensional FFT is the same as a 1-D FFT with the size of the product of the dimensions, except that the twiddle factors are different. So it naturally follows that the computational complexity is the same.

Mysticial
  • 464,885
  • 45
  • 335
  • 332