[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: A faster FFT of real matrices ??
From: |
THOMAS Paul Richard |
Subject: |
Re: A faster FFT of real matrices ?? |
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