{"id":555,"date":"2012-05-01T17:06:59","date_gmt":"2012-05-01T21:06:59","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=555"},"modified":"2019-10-31T14:47:07","modified_gmt":"2019-10-31T18:47:07","slug":"the-dft-matrix-and-computation-time","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2012\/05\/01\/the-dft-matrix-and-computation-time\/","title":{"rendered":"The DFT matrix and computation time"},"content":{"rendered":"
\r\n

On my list of potential blog topics today I saw just this cryptic item labeled dftmtx<\/tt>. Hmm, the MATLAB dftmtx<\/tt> function. But have I written about this function before? I better double-check by searching the old blog postings:\r\n <\/p>\r\n

<\/p>\r\n

Oh, I forgot about Loren's post!<\/a> She showed how the discrete Fourier transform, which MATLAB users normally compute by calling fft<\/tt>, can also be computed via a matrix multiply.\r\n <\/p>

x = rand(1000,1);\r\nX = fft(x);\r\n\r\nT = dftmtx(1000);\r\nX2 = T*x;\r\n\r\nmax(abs(X2(:) - X(:)))<\/pre>
\r\nans =\r\n\r\n   3.9790e-13\r\n\r\n<\/pre>
The difference is just floating-point round-off error.<\/p>\r\n   
My old post<\/a> talked about the value of having an independent computation method available when you are testing your algorithm.\r\n   <\/p>\r\n   
So today let's do something a little different. Let's compare the performance of computing the discrete Fourier transform\r\n      using the DFT matrix versus using the fast Fourier transform.\r\n   <\/p>\r\n   
To help with the timing, I'm going to use a function I wrote called timeit<\/tt> that you can download from the MATLAB Central File Exchange.\r\n   <\/p>
clear\r\nn = 100:50:3000;\r\nfor<\/span> k = 1:length(n)\r\n    nk = n(k);\r\n    x = rand(nk,1);\r\n    T = dftmtx(nk);\r\n\r\n    f = @() T*x;\r\n    g = @() fft(x);\r\n\r\n    times_f(k) = timeit(f);\r\n    times_g(k) = timeit(g);\r\nend<\/span>\r\n\r\nplot(n,times_f,n,times_g)\r\nlegend({'Using T*x'<\/span>, 'Using fft(x)'<\/span>})<\/pre> 
That's a pretty dramatic difference. The blue curve, showing the computation time using T*x<\/tt>, is an n^2 curve. Compared to that, the green curve, showing the computation time using fft(x)<\/tt>, is so low that you can hardly see it.\r\n   <\/p>\r\n   
Let's expand the y axis.<\/p>
ylim([0 0.0005])<\/pre> 
The lower green curve is an n*log(n) curve. The dramatic difference between that and the n^2 curve is why everyone got so\r\n      excited when the fast Fourier transform algorithm was invented (or re-invented<\/a>) a few decades ago.\r\n   <\/p>