Re: [eigen] A complex FFT for Eigen

["Benoit Jacob" <jacob.benoit.1@xxxxxxxxx>]

2008/12/1 Tim Molteno <tim@xxxxxxxxxxxxxxxxxxx>:
>> - replace for loops by Eigen expressions as much as possible
>>
>
> Agree that this is a useful goal, but I see this as a longer-term development.
> Once the FFT and testharnesses are solidly there, then this is best done
> hand-in-hand with benchmarking tools. There are also many many people out
> there who know far more than I about vectorizing FFT code.

Nevermind what I said... I looked back at the for loop,

                for (unsigned i=0; i<N2; i++)
		{
			std::complex<T> temp(data[i+N2]*w);
			data[i+N2] = data[i]-temp;
			data[i] += temp;	
			w += w*wp;
		}

And I don't see any way to use Eigen expressions here, or to vectorize
that loop as such (again, no contiguous access).

The good thing is that that's one less thing to require before
inclusion in Eigen... the bad thing is that then I have no clue how
FFTW achieves better performance.

As for the other loop, in factorize(), we already discussed that it
can't be vectorized.

One thing perhaps to consider... if one expands by hand the case for
N=4 or N=8 then perhaps one can notice some reordering of operations
allowing to vectorize things or at least reduce the number of
load/store.

> I don't think that all the 3 goals

2 remain... sorry for the noise.

> will be met for quite some time --
> particularly the dynamic sizes and the fftw backend. However, I'll start over
> the next few days putting together a module, using the LU code as a model

Great, looking forward to it.

Cheers,
Benoit

---