Reply by Scott Seidman May 29, 20072007-05-29
Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote in
news:UkJ6i.5908$C96.3051@newssvr23.news.prodigy.net: 

> > > Vista wrote: > > >> >> Please give me some pointers! I desperately need speed. The FFT is >> fast but when you run it millions of times it's still very very >> slow... Thanks a lot! >> > > Optimize the algorithm, not the code. Apparently you are trying to > accomplish something by the brute force; look for the smarter > approaches. > > Vladimir Vassilevsky > > DSP and Mixed Signal Design Consultant > > http://www.abvolt.com >
On top of this, don't neglect to optimize the code! Profile the code to make sure the fft is really your bottleneck. Make sure input and output arrays are preallocated, not growing or shrinking, or any other famous Matlab time eaters. -- Scott Reverse name to reply
Reply by Steven G. Johnson May 29, 20072007-05-29
On May 28, 5:17 pm, "Vista" <a...@gmai.com> wrote:
> Matlab's "fft" function is of course highly optimized over the years... > > Will I be able to speed it up by a factor of at least 10, by using a > third-party C/C++ or Fortran FFT/IFFT program that is callable from within > Matlab?
Matlab uses FFTW (www.fftw.org), but (last I heard) it pays a substantial overhead because it does a separate copy from Matlab's data structures to FFTW, especially for multi-dimensional FFTs. Also, although FFTW can use SSE/SSE2 instructions, I'm not sure Matlab exploits this; last I heard, Matlab's internal data allocation was not sufficiently aligned (16-byte aligned) to use this feature. So, on an x86 processor, you might be able to get a factor of (I'm guessing) 2 by calling FFTW (or perhaps Intel MKL, which has comparable performance) directly from a C progam (or similar). More, if you are able to get away with single precision. (This is often possible, as FFT algorithms such as those used in FFTW are very numerically stable, with fp errors growing at worst logarithmically with problem size.) It depends strongly on the size of the FFT that you need to perform, but I doubt that you will get a factor of 10. However, whether you are able to get this performance gain from a Mex plugin is another matter entirely. From a Mex program, you suffer from the same difficulties (in data formats, alignment, etc) that Matlab does. And, as the other posters on this thread have noted, it is likely to be more fruitful to examine other parts of your algorithm, to see whether you can get away with calling the FFT less often, or with smaller sizes, etc. (assuming your time is really dominated by the FFT). Regards, Steven G. Johnson
Reply by Tim Wescott May 28, 20072007-05-28
On Mon, 28 May 2007 14:17:22 -0700, Vista wrote:

> Matlab's "fft" function is of course highly optimized over the years... > > Will I be able to speed it up by a factor of at least 10, by using a > third-party C/C++ or Fortran FFT/IFFT program that is callable from within > Matlab? > That's to say, I try to find a third-party program, and modify it into a MEX > format, and compile it, and then call this function from within Matlab. Will > I be able to get the desired speedup? How much gain will I achieve? Is there > a very good third-party FFT/IFFT program in C/C++/Fortran that is both > fast and accurate and robust? > > Please give me some pointers! I desperately need speed. The FFT is fast but > when you run it millions of times it's still very very slow... Thanks a lot!
Vladimir beat me to the basic message: you should be thinking of ways to optimize your algorithm. The FFT is so general that some folks seem to think that all signal analysis is done with it -- this is not so. You should think in terms of the information you really need out of your signal, and how to get it. Then if the FFT is the only way, go ahead secure in the knowledge that you're working with a Really Hard Problem. So what is your signal like, and what are you trying to get out of it? Are you mostly analyzing low frequency phenomena? Then perhaps doing some prefiltering is the way to go. CIC (I think I have that right) filters seem to be pretty popular, and should go fast on a Pentium. Are you just interested in one frequency, or one frequency band? Then perhaps you want to do a one-frequency DFT (AKA demodulate and sum), or just a few. I don't want to make any more guesses -- my point is that there should be things that you can do, that may well be more efficient than the FFT/postprocessing approach that most people envision when they think of signal analysis. -- Tim Wescott Control systems and communications consulting http://www.wescottdesign.com Need to learn how to apply control theory in your embedded system? "Applied Control Theory for Embedded Systems" by Tim Wescott Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html
Reply by Vladimir Vassilevsky May 28, 20072007-05-28

Vista wrote:


> > Please give me some pointers! I desperately need speed. The FFT is fast but > when you run it millions of times it's still very very slow... Thanks a lot! >
Optimize the algorithm, not the code. Apparently you are trying to accomplish something by the brute force; look for the smarter approaches. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by Rune Allnor May 28, 20072007-05-28
On 28 May, 23:17, "Vista" <a...@gmai.com> wrote:
> Matlab's "fft" function is of course highly optimized over the years... > > Will I be able to speed it up by a factor of at least 10, by using a > third-party C/C++ or Fortran FFT/IFFT program that is callable from within > Matlab? > That's to say, I try to find a third-party program, and modify it into a MEX > format, and compile it, and then call this function from within Matlab. Will > I be able to get the desired speedup?
Probably not. Matlab uses FFTW which, as I understand, is one of the fastets (if not *the* fastest) FFT packages available.
> How much gain will I achieve?
Very little, if any.
> Is there > a very good third-party FFT/IFFT program in C/C++/Fortran that is both > fast and accurate and robust?
FFTW. But you already have it.
> Please give me some pointers! I desperately need speed. The FFT is fast but > when you run it millions of times it's still very very slow... Thanks a lot!
The one thing you can do, which might make a difference, is to make sure you use the parallel version of FFTW if you have a multi-core computer. Apart from that, well, start the data processing when you leave your office or desk at night, and get the results in the morning. Rune
Reply by Vista May 28, 20072007-05-28
Matlab's "fft" function is of course highly optimized over the years...

Will I be able to speed it up by a factor of at least 10, by using a
third-party C/C++ or Fortran FFT/IFFT program that is callable from within 
Matlab?
That's to say, I try to find a third-party program, and modify it into a MEX
format, and compile it, and then call this function from within Matlab. Will
I be able to get the desired speedup? How much gain will I achieve? Is there
a very good third-party FFT/IFFT program in C/C++/Fortran that is both
fast and accurate and robust?

Please give me some pointers! I desperately need speed. The FFT is fast but 
when you run it millions of times it's still very very slow... Thanks a lot!