How to show that DFT follows N^2 number of operations?
1 visualización (últimos 30 días)
Mostrar comentarios más antiguos
Raushan
el 22 de Sept. de 2022
Comentada: Chunru
el 23 de Sept. de 2022
Hey!
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.
0 comentarios
Respuesta aceptada
Chunru
el 23 de Sept. de 2022
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 comentarios
Más respuestas (0)
Ver también
Categorías
Más información sobre Spectral Measurements en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!