Speed up FFT calculation

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!

Answer 1

[dpb]

"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.

[Steven Lord]

Instead of transposing the input, try using the dim third input to fft.

[William Gray]

Hi Steven,

thank you for the answer!

I will try transposing the signal before completing the FFT to see if this speeds things up.

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

[Steven Lord]

The dim argument tells MATLAB over which dimension to compute the FFT (by rows, by columns, by pages, etc.)

[dpb]

"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]

Earlier I wrote "Your use of ones to preallocate probably also hurt instead of helped since the output array needs to be complex," but I neglected to mention the big thing besides the type mismatch is you then wrote inside you loop:

SignalF = fft(Signal(i,:));

In which you didn't refer to the allocated array to store the coefficients into by row but redefined it every pass.

So, also in the end you only have left the very last row coefficients -- you've overwritten the first 36349 and wasted all those compute cycles.

[William Gray]

Sorry to be a pain, but I don't quite understand how I am not refering to the allocated store 'SignalF' when that is the same name as my variable inside the loop?

Would it be easy for you to write the code so I could see?

Again thank you for the help, it's really useful and really appreciated

[dpb]

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]

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]

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