[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
A faster FFT of real matrices ??
From: |
David Bateman |
Subject: |
A faster FFT of real matrices ?? |
Date: |
Wed, 28 Jan 2004 15:45:23 +0100 |
User-agent: |
Mutt/1.4.1i |
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
- A faster FFT of real matrices ??,
David Bateman <=