How to show that DFT follows N^2 number of operations?

조회 수: 1 (최근 30일)
Raushan . 2022년 9월 22일
댓글: Chunru . 2022년 9월 23일
Let's say I have a matrix with 4096 data in one column.FIrst, I took 256 data from that to perfom DFT(without FFT) and FFT both and record the time needed for each operation. Then I took 1 to 512 data and do the same. Similarly I took 1 to 1024 data to perform the same operation and kept going like this till 4096.
It is known that number of operations for FFT follows N logN trend (where N is the sample size) and DFT follows N^2 trend. I am trying to plot for time required for each operation vs number of sample and somehow show that they follow the trends as mentioned. I am not understanding if I should do a polyfit or just loglog plot for both axes and see the curve is linear for both cases or not. What should I do in this case?
Any help will be appreciated.

채택된 답변

Chunru 2022년 9월 23일
One simple way is to plot sqrt(dft_time) vs n to see if it is a straight line.
Generally speaking, the computation time can be a very complicated thing. The DFT/FFT computations not only depending on the number of mulitplication/addtions (N^2 and N*log2(N)), but also depend on how the coefficients are computed and how memory are accessed (espcially with cache memory structure) and how index are generated, never mentioning the overhead of fft implementation in matlab.
  댓글 수: 5
Chunru 2022년 9월 23일
See the update for fitting.

댓글을 달려면 로그인하십시오.

추가 답변 (0개)


Help CenterFile Exchange에서 Spectral Measurements에 대해 자세히 알아보기




Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by