This project has moved. For the latest updates, please go here.

Discrete Fourier Transform

Coordinator
Aug 7, 2009 at 11:50 AM

Hi,

I started porting FFT from Iridium. Except it's actually a complete rewrite, and we'll finally have fast DFT support for arbitrary N (not power-of-two only).

Naturally it would be interesting to provide optional native high-performance versions as well.

I noticed that MKL provides very well performing FFT routines, so I think in the MKL case we could/should use them. However, I guess the other native libraries do not provide any such routines? Should we try to integrate FFTW3 (GPL!) instead in this case?

Thanks,
Chris

Aug 7, 2009 at 12:28 PM

Hi Chris.

>Naturally it would be interesting to provide optional native high-performance versions as well.

FFT should be one of the interface/factory algorithms.  We should probably decide if we are going to go that route or not.  So far you and I are in favor of it.
Patrick, Jurgen, and Max - What do you think?

>I noticed that MKL provides very well performing FFT routines, so I think in the MKL case we could/should use them. However, I guess the other native libraries do not provide any such >routines? Should we try to integrate FFTW3 (GPL!) instead in this case?

ACML does, but I think FFTW is the only vectorized open source library.  We could offer a non-vectorized native version for the ATLAS/LAPACK/BOOST build.

This also shows a weakness of my current proposal - that is all native bundles (MKL, ACML,ATLAS/LAPACK/BOOST, CUDA/BOOST, etc.) have to provide exactly the same functionality.  A previous propsal broke up the functionanlity (i.e. LinearAlgrebra, RandomeNumbers, FFT, etc).  That is much more flexible.  We could even provide a FFTW FFT provider for those that were OK with the GPL.

If we broke things up, we could have the following native providers:

Linear Algebra:

  • MKL
  • ACML
  • ATLAS/LAPACK
  • Eigen
  • CUDA

Random Numbers:

  • MKL
  • ACML
  • BOOST

FFT:

  • MKL
  • ACML
  • FFTW 
  • CUDA

Vector Math:

  • MKL
  • ACML
  • CUDA?

Drawbacks of course are more complex wrapping code and more native DLLs.

We should probably also decide on this relatively soon.  Fixed bundles all providing the same functionality or a provider plug-in approach? dnA has tried both approaches, each had its own unique problems.

Thoughts? I'm not sure.  

Thanks,

Marcus

 

Coordinator
Aug 7, 2009 at 2:45 PM

I like a fixed-bundles approach; this way we can fall back on managed methods if we think there is no good alternative in the native implementation. I think this was how the latest versions of dnA worked. The plugins are cool but I guess it would require having various dll's lying around. Also, it seems harder to test as there are so many more combinations; with bundles we only need to test one fixed set of packages.

Hopefully I'll have time to look at your proposal over the weekend Marcus. Been some busy weeks here ...

Cheers, J

Aug 7, 2009 at 2:55 PM

>I like a fixed-bundles approach; this way we can fall back on managed methods if we think there is no good alternative in the native implementation.

I guess I wasn't clear (as usual).  It is an all or nothing approach with the fixed bundles. For each bundle. we have to implement every algorithm interface we define (ILinearAlgebra, IRandomNumbers, IFFT, etc).  In the case of FFT, we'd have to write our native implementation or find an X11 comaptible one that we can use with an ATLAS or Eigen based bundle.

Regards,

Marcus

Aug 12, 2009 at 9:33 AM
Edited Aug 12, 2009 at 5:47 PM

Hi Guys,

A drawback to the individual provider approach is that we have to duplicate the managed/native wrapper for each provider (limitation of P/Invoke). This blog post got me thinking - http://tirania.org/blog/archive/2009/Aug-11.html .  Since we are not using .NET 4 we cannot do as the blog post does exactly, but I think we can replicate the functionality using reflection - that is building a managed/native wrapper at runtime. Then we'd only need one wrapper (assuming each provider DLL exported the same functions).  I'm going to tinker with this idea to see what impact it will have on performance.

Regards,
Marcus

 

 

Aug 13, 2009 at 12:00 PM

OK, I started writting the code and then I realized how stupid it is.  Why create the wrappers at runtime when you can have a code generator create all the wrappers once (and when they need to be updated) and them to the source repo. duh!

 

Apr 4, 2011 at 10:53 PM

Quick question - the FFT available in the current code only supports power-of-two N correct ? I'm using RealFourierTransformation.TransformForward.

Thanks !

Coordinator
Apr 5, 2011 at 8:00 AM

Hi dondestasmanu,

No, the FFT routines in Math.NET Numerics support arbitrary vector lenths, not just power-of-two, see Linear Integral Transforms.

However, "RealFourierTransformation" sounds like you're using the old Math.NET Iridium instead of Math.NET Numerics (which replaces Iridium). Iridium indeed did support only power-of-two vector lengths. You may want to upgrade to Math.NET Numerics.

Thanks,
Chris