Re: A faster FFT of real matrices ??

[THOMAS Paul Richard]

Dmitri and David,

This is not a fault with FFTW; it is intrinsic to the method they use.  The
basis space is factored into prime numbers and the FFT carried out using
primes to powers, rather than just 2 to a power.  It's great until prime
numbers get to be large.  514 factors to 257, which is prime.  Try 521 and
523, which are themselves prime.  I find a factor 4 slow-down relative to
522. By the time you get to 1031(prime),1032 & 1033(prime), the slow-down is
a factor 9.  As a general rule, avoid doing FFTs on anything other than 2^N
bases, no matter how clever the algorithm.  FFTW seems to perform well with
products of powers low order primes but once the primes get into the
hundreds, you pay.

Sincerely

Paul THOMAS

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.564 / Virus Database: 356 - Release Date: 19/01/04