Speed up FFT calculation

Question

William Gray 2020-6-22

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/552676-speed-up-fft-calculation

评论： dpb 2020-6-23

采纳的回答： dpb

在 MATLAB Online 中打开

Hello everyone,

I'm currently struggling to speed up an FFT calculation within a for loop for a repeating signal.

the signal matrix is 36350x2048, 36350 being the number of signals and 2048 being the zero padded length of each signal. I padded each signal to this length in hopes that being a power of 2 would speed the calculation up. I also create a matix of ones to attempt to speed up the calculation.

My code for completeing this fft is very simple, but shown below:

SignalF = ones(36350,2048); %create empty matrix
for i = 1:NumS; %pepeat for number of signals
    SignalF = fft(Signal(i,:));
end

However, I have found that for this size signal matrix, the calculation is taking around 30 minutes or so (I haven't actually timed it) but I have lots of these matracies to process and so need a way of speeding this up.

Any thoughts or ideas would be really appreciated!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

dpb 2020-6-22

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/552676-speed-up-fft-calculation#answer_455395

在 MATLAB Online 中打开

"The signal matrix is 36350x2048, 36350 being the number of signals and 2048 being the zero padded length of each signal. "

Use the vectorized form TMW supplied --

Y=fft(Signal.');

From the documentation...

Y = fft(X) computes the discrete Fourier transform (DFT) of X using a fast Fourier transform (FFT) algorithm.

If X is a matrix, then fft(X) treats the columns of X as vectors and returns the Fourier transform of each column.

Reorient the input array by columns instead of by rows. You can test for comparison but the power of two probably won't make that big a difference (altho I've not timed anything this large to see, granted).

Your use of ones to preallocate probably also hurt instead of helped since the output array needs to be complex, not real -- I also didn't test that hypotheis as there's no need since you can (and should) build the full output array using array syntax.

9 个评论
显示 7更早的评论隐藏 7更早的评论

dpb 2020-6-22

编辑：dpb 2020-6-22

在 MATLAB Online 中打开

"I'm not sure how I'd use a third dimension here, the matrix is only in 2 dimensions?"

It's not 3rd dimension, it's the third (optional) input that specifies the dimension of the array over which to operate.

fft(x.')

and

fft(x,size(x,2),2)

will be same thing. The one difference is the orienation of the coefficients will also be by row instead of by column -- but I'd expect that then would have similar performance-reducing effects when comes to using the output. I think it would be better to use the MATLAB column-order convention from the git-go that almost all data functions are built around of operating column-wise by default. Just makes sense from storage order to me, anyways...

Steven, I figured that the above syntax would just result in a transpose operation inside fft() anyway, won't it?

If it doesn't, I'd expect it to be much slower by operating across a stride rather than by natural array order.

I didn't test and since FFT is builtin, one can't see what the preamble code before passing to the core routines does.

dpb 2020-6-22

在 MATLAB Online 中打开

You are referring to the variable, yes -- the problem in what you wrote is that the LHS is not subscripted so by MATLAB syntax the entire variable is reallocated to the RHS on assignment. Hence, you are redefining the entire array every pass to the output of the one-row calculation.

Try a small sample case that won't take much time -- the problem will be apparent in that the output will only be 1xN, not MxN as you expect.

The only reason to bring this up is as explanation as to what is probably one the bigger time bottlenecks in the code you wrote; the correct answer/solution is to not use loop at all nor to preallocate a variable you're just going to overwrite in its entirety anyway.

While you do NOT want to do this, what your code should have looked like would have been something like

[NumS,NumCol]=size(Signal);                     % get array size
nFFT=2^nextpow2(NumCol);                        % set the FFT size for signal size
SignalF=complex(zeros(numS,nFFT));              % preallocate complex array of right size
for i = 1:NumS
  SignalF(i,:) = fft(Signal(i,:));              % store into preallocated array
end

AGAIN, DO NOT DO THIS!!! USE THE ARRAY SYNTAX INSTEAD!!!!!!!!!!!!!

I still recommend that you should rearrange your data storage to use column-oriented arrangement where the signals are column and the observations are rows. That matches up with the inherent MATLAB convention used almost univerally.

William Gray 2020-6-23

Thank you very much for all you're help, it is now clearer what the issue is.

I have managed to re-write the code no longer using a loop at all and you are right, it is much quicker!

dpb 2020-6-23

Did you test the two orientations and/or the 3rd argument variations to see difference in speed the memory layout might make?

请先登录，再进行评论。

Speed up FFT calculation

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

9 个评论
显示 7更早的评论隐藏 7更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

Speed up FFT calculation

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

9 个评论 显示 7更早的评论隐藏 7更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

9 个评论
显示 7更早的评论隐藏 7更早的评论