Re: [eigen] A complex FFT for Eigen

On Fri, Nov 28, 2008 at 11:02 AM, Tim Molteno <tim@xxxxxxxxxxxxxxxxxxx> wrote:

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.

interesting ! for which sizes ? which scalar type (float or double) ? I guess such a templated code is particularly well suited for small sizes....

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.

sorry, by 32 I meant N=5 (2^5 = 32)