Faster FFTs, FFTW3 and FFT's of Nd

[David Bateman]

Well I know I went quiet on what I was doing with the FFTW stuff since
my last patch about 2 weeks ago. The fact is I've not really had that
much time and still don't for that matter. However, having
investigated a little a couple of weeks ago, I then noticed Matlab has
Nd array support for the FFTs and it didn't seem worth touching the
fft code without also doing this support at the same time.  I now have
working FFTW3 and Nd array support for Octave. That is

* '(i)fft' now accepts a third argument for the dimension of the matrix over 
  which to do the FFT, and accepts Nd arrays.
* '(i)fft2' accepts Nd arrays, and does 2d FFTs over each 2d sub-matrix
* Added a new function '(i)fftn' that performs Nd FFTs over Nd matrices.
* Added a new function 'fft_wisdom' that is used to manipulate FFTW wisdom
  data.
* Readded storage of plans for FFTW3, since this appears to help for small
  FFTs.

Basically this code is not quite ready for inclusion yet. For the following
reasons

* The FFTPACK backup code for the Nd array stuff in {d|C}NDArray.cc has
  not even been compiled yet, let alone tested.
* The 'fft-wisdom' function can't yet create wisdom itself. It can only
  import wisdom from external sources.
* Although I've tested the code extensively for the 1 and 2d cases so as to
  not have regressions and to see that I get at least the same or better
  speed, the Nd stuff hasn't been torture tested yet.

So this mail is also looks for people who have some good Nd array fft cases
to check this code against, and to ask advice on how to deal with the
issues of FFTW wisdom data.

For testing purpose please find attached a patch against 2.1.53, and my 
current test code. You'll need to call 'autogen.sh' to recreate the 
'configure'script. Also I've now completely dropped the FFTW2 support,
so you'll need a new version of FFTW3 installed. If you have examples 
to compare this patch in Octave against Matlab Nd array examples, this
would be great.

For the wisdom data it seems best to use the supplied external program 
"fftw-wisdom" that comes with FFTW3 to create the needed wisdom within
octave. Too much code would have to be cut out of this and inserted into
octave otherwise. However how can an external program be called portably
from within Octave? Does anyone have any examples?

Regards
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