From octave-maintainers-request at bevo dot che dot wisc dot edu Thu Jan 29 07:00:28 2004 Subject: Re: A faster FFT of real matrices ?? From: THOMAS Paul Richard To: "'dmitri at unm dot edu'" , "'David.Bateman@motorola.com'" Cc: "'octave-maintainers at bevo dot che dot wisc dot edu'" Date: Thu, 29 Jan 2004 02:45:29 -0600 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