[Numpy-discussion] performance of real_fft with fftpacklite.c

[Bernd Rinn]

Hello,

does anyone know why the performance of FFT.real with fftpacklite.c is
so unballanced for n=2**i and different values of i? My example is:

=======================================================================
from Numeric import array,Float
from FFT import real_fft
from time import time

i=1
while i<20:
    n = 2**long(i)  
    a=array(range(long(1),n),Float)
    anfang = time()
    b = real_fft(a)
    ende=time()
    print "i=", i, " time: ", ende-anfang
    i+=1
=======================================================================

and the result shows (on a Pentium-III-700 under Linux):

=================================================================
i= 1  time:  0.000182032585144
i= 2  time:  0.000133991241455
i= 3  time:  0.00012195110321
i= 4  time:  0.000123977661133
i= 5  time:  0.000131964683533
i= 6  time:  0.000155925750732
i= 7  time:  0.000362992286682
i= 8  time:  0.000240921974182
i= 9  time:  0.000506043434143
i= 10  time:  0.00064492225647
i= 11  time:  0.00177395343781
i= 12  time:  0.0025269985199
i= 13  time:  0.886229038239
i= 14  time:  0.0219050645828
i= 15  time:  0.0808279514313
i= 16  time:  0.327404975891
i= 17  time:  482.979220986
i= 18  time:  0.803207993507
i= 19  time:  7782.23972797
=================================================================

when I am using an array a of length 2**19 and giving the command

b=real_fft(a,n=2**long(20))

the time drops from over two hours CPU-time to about 1.5 seconds.

I know that fftpacklite.c is not specially optimized, but isn't a
FFT method with vectors lenghts that are powers of 2 be supposed to
show a more predictible run-time behavior?

Could perhaps anyone point me to a free FFTPACK FORTRAN package for
Linux with g77 that performs better than the default package? 

Any hint would be greatly appreciated.

Best regards,

Bernd Rinn

P.S.: Please CC to Bernd.Rinn at uni-konstanz.de since I am not a member
      of the list.
-- 
Bernd Rinn
Fakultät für Physik
Universität Konstanz

Tel. 07531/88-3812, 
e-mail: Bernd.Rinn at uni-konstanz.de
PGP-Fingerprint: 1F AC 31 64 FF EF A9 67  6E 0D 4C 26 0B E7 ED 5C