Re: [eigen] A complex FFT for Eigen

[Tim Molteno <tim@xxxxxxxxxxxxxxxxxxx>]

Gael Guennebaud wrote:
> First of all, I'm 100% OK to provide a Fourier module in Eigen. My 
> issues are more about how to do it. Looking at FFTW benchmarks, it is 
> pretty clear to me that we *must* provide support for it. 
Agreed. Mind you, I'd also love to see how fast a templated C++ bit of 
code could go! I've done a quick check and we're about 50% as fast as 
fftw at the moment. I think that some vectorization might well get us 
quite a bit closer.
> So, in the same vein of the other modules, I would provide a default 
> implementation based on Tim's lightweight source code such that we can 
> make the dependency to FFTW optional for most use cases of this 
> module. Of course this requires to extend a bit Tim's code to support 
> at least: real data, dynamic sizes, 1D and 2D data (I guess all are 
> trivial to add). IMO non pot sizes is not mandatory.
>
> About current Tim's code, what about adding a specialization of 
> Radix2_Decimation<> for sizes greater than, let's say 32, which would 
> use normal recursive calls untill the size is 32. This would 
> automatically add support for dynamic sizes, and significantly reduce 
> the size of the generated code.
I suspect that any computer out there today would take months to do an 
FFT of a matrix of length 2^32! So it might be more sensible to just 
return an error!

I've done specializing at N=2 for a small speedup. I didn't include it 
as it just cluttered the code.

Cheers

Tim

---