A faster FFT of real matrices ??

[David Bateman]

I've implemented FFT's over real matrices in octave with FFTW 2.1.5 and
I can achieve a speed up of about a factor of 2. However, in some cases
I'm also getting slower code fft(randn(514)) is a case in point. 

Basically, I can't see why this is happening, and so this e-mail is a
call for help. What I think is happening is that my libfftw.so was
compiled by someone else and so isn't optimal for my machine, (does 
FFTW build optimize for cache size?). So what I was hoping was to see
if someone might like to test the attached patch against 2.1.53, with
the test programs.

There are two test programs. The procedure to use the test code, is to
run "testfft.m" on an unpatched version of 2.1.53, and then run "testfft2.m"
on a patched version. You'll see something like

Loading Data       done
Testing fft(  512,  512)   4.00e-02 sec (5.06e-01) rerr 2.69e-13
Testing fft2(  512,  512)  8.06e-02 sec (4.90e-01) rerr 2.06e-13
Testing fft(  513,  513)   8.94e-02 sec (5.90e-01) rerr 3.35e-13
Testing fft2(  513,  513)  1.65e-01 sec (6.77e-01) rerr 1.64e-13
Testing fft(  514,  512)   4.01e-01 sec (2.60e+00) rerr 2.88e-12
Testing fft2(  514,  512)  4.41e-01 sec (2.45e+00) rerr 1.37e-13
Testing fft(  512,  514)   4.01e-02 sec (4.97e-01) rerr 1.63e-12
Testing fft2(  512,  514)  1.18e-01 sec (4.69e-01) rerr 5.56e-13
Testing fft(65536,    1)   2.82e-02 sec (7.83e-01) rerr 4.17e-14
Testing fft2(65536,    1)  2.81e-02 sec (6.57e-01) rerr 4.17e-14

Where the first value is the run time on the current version, the second 
is the relative runtime to the previous version and "rerr" is the relative
error. As I save in ascii (I'm using 2.1.50 as my old test veresion), you
can't expect better relative errors than about 1e-13 or so.

As you can see the speed of the new code is better in the cases tested except
n=514, where it is 2.5 times slower!!!! It would be nice to understand what 
is happening here, as matlab doesn't seem to have this problem and runs at
the union of the lowest speeds on the two versions of the octave fft code.

Cheers
David

-- 
David Bateman                                address@hidden
Motorola CRM                                 +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary

testfft.m
Description: Text document

testfft2.m
Description: Text document

patch
Description: Text document