Working patch for FFTW 3.0.x and Nd FFT's

[David Bateman]

Dear All,

Please find attached a working patch for FFTW 3.0.x support and Nd
FFTs.  This patch also shows a significant speed up from the previous
code, with the proviso that the canonical FFTW wisdom has been
generated and installed in a system dependent file (/etc/fftw/wisdom
on my machine).

The testing of the code was done in a hierarchical fashion. Firstly I
showed that the "fft", "fft2", "ifft" and "ifft2" commands returned the
same results as previously. This was done by running the supplied script
"testfft.m" on an unpatched octave or even matlab, and then running the
script "testfft2.m" on a patched version of octave. This also gave the 
relative speed of the version of the code, which I supply in the file "log".

The final level of testing was to test the Nd array support. Firstly
"fft(x,[],n)" are tested by taking 2-D slices through the data and
using the already tested fft over 2d data sets to prove that these
work. "fft2(x)" was tested in the same manner. To test "fftn(x)", the
formula

b = a;
for i=1:length(size(x))
  b = fft(b,[],i);
endfor

is equivalent and as the Nd fft's has been tested to be correct, the test 
of fftn is then also completed. A similar series of tests was performed 
for the inverse transforms. The test script is "testfft3.m" and is also 
attached. Tests were performed of a series of 3d data as well as a 4d
data set.

Some provisos for the patches use

* You must upgrade to FFTW 3.0.x due to an API change between version 2
  and 3. If you don't upgrade the slower FFTPACK version of the code
  (that have also been tested) will be used.
* Although not necessary, running 
    mkdir /etc/fftw
    fftw-wisdom -v -c -o /etc/fftw/wisdom 
  is highly recommended. This will take a long time (12 hours + on my machine)
* The new function "fft_wisdom" can be used to manipulate and create the 
  wisdom necessary for Octave. This is also incredible slow due to its use
  of "fftw-wisdom" internally.

Given all of the testing I've given the code, I now consider this
patch ready for inclusion into 2.1.54....

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

log
Description: Text document

testfft2.m
Description: Text document

testfft3.m
Description: Text document

patch
Description: Text document