MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Fourier and FFT: Powers of 2 only?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg16104] Re: Fourier and FFT: Powers of 2 only?
  • From: Robert Knapp <rknapp>
  • Date: Thu, 25 Feb 1999 08:25:00 -0500
  • Organization: Wolfram Research, Inc.
  • References: <7a29pk$1pm@smc.vnet.net> <7ag1cm$aef@smc.vnet.net> <7ao3lc$ruk@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

For Mathematica version 3, John Doty is correct...

John Doty wrote:
> 
> Fourier[] uses a "mixed radix" FFT algorithm, in which the transform is
> decomposed into subtransforms whose lengths are the prime factors of the
> length of the data set. The efficiency of this procedure depends on
> small the factors are. The best is when the length is a power of 2:
> 
> In[8]:=
> Timing[Fourier[Take[dat,65536]];]
> 
> Out[8]=
> {2.08333 Second,Null}
> 
> The worst is when the length is prime:
> 
> In[9]:=
> Timing[Fourier[Take[dat,65537]];]
> 
> Out[9]=
> {5673.85 Second,Null}
> 
> It's still pretty good if all the factors are small, even if you can't
> get all the way down to 2:
> 
> In[10]:=
> Timing[Fourier[Take[dat,64000]];]
> 
> Out[10]=
> {3.8 Second,Null}
> 

In the version under development a number of improvements have been made
which will make Fourier generally faster, and changes the situation in a
number of ways.

For the general case, it will still use a mixed radix algorithm

For lengths which are products of small primes (also 4,8,16 and 9) it
uses a self-sorting prime factor algorithm, (after Temperton), which in
many cases is faster that even the radix 2 with bit reversal.  

For large prime factors it uses an algorithm which is about three times
slower than for a nearby factorable number, but much faster than the
usual O(n^2) algorithm for prime factors.

Rob Knapp
Wolfram Research


  • Prev by Date: Stop palette opening
  • Next by Date: Using "Fit"
  • Previous by thread: Re: Fourier and FFT: Powers of 2 only?
  • Next by thread: Re: Bug?