Prev: Problem with gath geva algorithm
Next: geometry profile in pde tool.
From: Lei on 27 Mar 2010 02:42
The Matlab build-in function "fft" is a highly efficient algorithm for fast implementation of the Fourier transform. However, in some situations I do not need the calculate the full-point FFTs every time. Suppose I only need to calculate a subset of outputs, I have to develop a partial FFT (i.e. fractional FFT, or pruned FFT) algorithm. Actually I developed a partial FFT algorithm in an M-file, but the computation speed is far lower than the build-in "fft".

I need some tips on how to accelerate the computation speed of the partial FFT algorithm, it should be faster than the "fft" function. For example, if I only need to calculate the first output X(0) of a 1024-point FFT, my partial FFT algorithm should be faster than the standard "fft" algorithm. I need to explore possible code optimization for my partial FFT algorithm.

Is there someone who can help me cope with this problem? I can be reached at mikej.edu(a)gmail.com
Thanks.
From: TideMan on 27 Mar 2010 06:34
On Mar 27, 7:42 pm, "Lei " <mikej....(a)gmail.com> wrote:
> The Matlab build-in function "fft"  is a highly efficient algorithm for fast implementation of the Fourier transform. However, in some situations I do not need the calculate the full-point FFTs every time. Suppose I only need to calculate a subset of outputs, I have to develop a partial FFT (i.e.. fractional FFT, or pruned FFT) algorithm. Actually I developed a partial FFT algorithm in an M-file, but the computation speed is far lower than the build-in "fft".
>
> I need some tips on how to accelerate the computation speed of the partial FFT algorithm, it should be faster than the "fft" function. For example, if I only need to calculate the first output X(0) of a 1024-point FFT, my partial FFT algorithm should be faster than the standard "fft" algorithm. I need to explore possible code optimization for my partial FFT algorithm.
>
> Is there someone who can help me cope with this problem? I can be reached at mikej....(a)gmail.com
> Thanks.

And I want to spin straw into gold.
I have a spinning wheel and several bales of straw, but no matter how
hard I try it doesn't work.
Is there someone who can help me with this problem?
I can be reached at rumpelstiltskin(a)gmail.com

From: Wayne King on 27 Mar 2010 08:15
"Lei " <mikej.edu(a)gmail.com> wrote in message <hok9bu$dcu$1(a)fred.mathworks.com>...
> The Matlab build-in function "fft" is a highly efficient algorithm for fast implementation of the Fourier transform. However, in some situations I do not need the calculate the full-point FFTs every time. Suppose I only need to calculate a subset of outputs, I have to develop a partial FFT (i.e. fractional FFT, or pruned FFT) algorithm. Actually I developed a partial FFT algorithm in an M-file, but the computation speed is far lower than the build-in "fft".
>
> I need some tips on how to accelerate the computation speed of the partial FFT algorithm, it should be faster than the "fft" function. For example, if I only need to calculate the first output X(0) of a 1024-point FFT, my partial FFT algorithm should be faster than the standard "fft" algorithm. I need to explore possible code optimization for my partial FFT algorithm.
>
> Is there someone who can help me cope with this problem? I can be reached at mikej.edu(a)gmail.com
> Thanks.

Hi Lei,
Have you tried

>>doc goertzel

You can use the

dft_data = goertzel(data,freq_indices)

syntax to compute the DFT at only the specified frequencies. If you have that type of application, the Goertzel algorithm will often give you a lot of savings.

Wayne
From: Doug Schwarz on 27 Mar 2010 08:44
In article <hok9bu$dcu$1(a)fred.mathworks.com>,
"Lei " <mikej.edu(a)gmail.com> wrote:

> The Matlab build-in function "fft" is a highly efficient algorithm for fast
> implementation of the Fourier transform. However, in some situations I do not
> need the calculate the full-point FFTs every time. Suppose I only need to
> calculate a subset of outputs, I have to develop a partial FFT (i.e.
> fractional FFT, or pruned FFT) algorithm. Actually I developed a partial FFT
> algorithm in an M-file, but the computation speed is far lower than the
> build-in "fft".
>
> I need some tips on how to accelerate the computation speed of the partial
> FFT algorithm, it should be faster than the "fft" function. For example, if I
> only need to calculate the first output X(0) of a 1024-point FFT, my partial
> FFT algorithm should be faster than the standard "fft" algorithm. I need to
> explore possible code optimization for my partial FFT algorithm.
>
> Is there someone who can help me cope with this problem? I can be reached at
> mikej.edu(a)gmail.com
> Thanks.

Amazingly, The MathWorks has anticipated your need and has provided a
function to compute exactly the first element of the DFT. It is very
fast. Use it like this:

X0 = sum(x);

--
Doug Schwarz
dmschwarz&ieee,org
Make obvious changes to get real email address.
From: Matt J on 27 Mar 2010 09:03
"Wayne King" <wmkingty(a)gmail.com> wrote in message <hokssd$ntm$1(a)fred.mathworks.com>...

> Have you tried
>
> >>doc goertzel
>
> You can use the
>
> dft_data = goertzel(data,freq_indices)
>
> syntax to compute the DFT at only the specified frequencies. If you have that type of application, the Goertzel algorithm will often give you a lot of savings.
==================

This must be something from the Signal Processing Toolbox. I have no doc on a GOERTZEL command, at any rate.

I've never encountered the Goertzel algorithm before, although from this wiki article, it has obviously been around for a long time,

http://en.wikipedia.org/wiki/Goertzel

However, I can't really see what advantages it conveys over direct evaluation of the DFT. The computational complexity, as discussed in teh article, seems to be the same for both.
 |  Next  |  Last
Pages: 1 2 3
Prev: Problem with gath geva algorithm
Next: geometry profile in pde tool.