[eigen] FFT for Eigen

[Mark Borgerding <mark@xxxxxxxxxxxxxx>]

I've been thinking about porting/adapting my kissfft library for use in C++ (  http://sourceforge.net/projects/kissfft )

I am aware that there was a previous offering for an Eigen FFT library, but it seemed to suffer from a couple of a serious drawbacks. Namely, it could only perform power-of-2 transforms and the power of two was required at compile time.

A little about KISSFFT, since that is the library this would be based on. 

• arbitrary FFT sizes with optimized radix butterflies for factors 2,3,4,5
• arbitrary dimensions
• optimization for real-only case
  
• small code footprint
  
• reasonably good efficiency (within order of magnitude speed of FFTW and IMKL).
• can be compiled for fixed point or a variety of floating point (AFAIK, kissfft is the only free  fixed point FFT , period)
  
• easy going license (currently revised BSD style, for Eigen, I would be willing to use LGPL/GPL)
  

My thought for Eigen was to make a template fft class that would be specialized for: float, double, & long double, eventually maybe others (fixed point, extended precision classes?)
Much of the behavior would be relegated to a traits class which would be responsible for creating twiddle factors, deciding factorization, scaling, etc.  This should allow easy extension by users without requiring them to hack the library itself.


I've done a little bit of coding and little bit of thinking.  The interface is shaping up to something like:

template <typename T_Data,typename T_traits=kissfft_utils::traits<T_Data> >
class kissfft
{
    public:
        typedef T_traits traits_type;
        typedef T_Data scalar_type;
        typedef std::complex<scalar_type> cpx_type;

        kissfft(int nfft, const traits_type & traits = traits_type() );

       void fwd( cpx_type * dst, const cpx_type * src); // forward complex-to-complex transform
       void fwd( cpx_type * dst, const scalar_type * src);  // forward real-to-complex transform
       void inv( cpx_type *dst, const cpx_type * src);// inverse complex-to-complex transform
       void inv(scalar_type * dst, const cpx_type *src; // inverse complex-to-real transform
}

Also, my hope is to have #ifdef protected code that would use the kissfft library by default, but could also use FFTW or IMKL if it was so compiled (since they are much faster).

-- Mark