|Re: [eigen] A complex FFT for Eigen|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] A complex FFT for Eigen
- From: "Gael Guennebaud" <gael.guennebaud@xxxxxxxxx>
- Date: Fri, 28 Nov 2008 13:26:47 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:in-reply-to:mime-version:content-type:references; bh=n9GGlplJuy8KWrawEbq0JE+L7u9ORJbKcb2vXoRtGDA=; b=PPUR13qs5c2cZ9U4+gSsdtf+edVoOYotHZvOu6Wi/iao4ErFAEstSJm4XYBfH7r2P8 G3X+Jxwzut8Uyk2/rsR9AqbL/FOYMVhSPP+ESDymACcErbsXtEf+KzIDaYTCs+OkrkDy TSDiuygHQ/E5RYCgJeh+meVJI4vXtGWayJZxU=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:in-reply-to:mime-version :content-type:references; b=lI/6ar0C5h3uxScWTMAKzgWL/wqUyhhoMTYc0EbqEjB8CruUWbf2LjaolPnhuDmM/D YNlqGR/40Ltr0JNlgFRigZtaiS3SCmxIXPlX0x9UBlODsxjNh9v007GzzOVN9LqNF7km nXpn0YisxNxmcOTGStSO2Q0c2F9MjV4XTgJm0=
On Fri, Nov 28, 2008 at 11:02 AM, Tim Molteno <tim@xxxxxxxxxxxxxxxxxxx>
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.
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.
interesting ! for which sizes ? which scalar type (float or double) ? I guess such a templated code is particularly well suited for small sizes....
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!
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'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)