FFT Algorithm Variation

[Peter_APIIT]

Hello to all, as you all know FFT algorithm has many variation in terms from its pruposes.

My requirement of FFT is integer multiplication and polynomial evaluation.

I looking for good reference about the topic.

If you have any, please post it here.

Thanks.

[daviddoria]

I don't think this is really a c++ question at all, sorry Peter.

[Peter_APIIT]

I want to code in C++.

[StuXYZ]

Well the basic FFTs are available in the GSL (gnu-scientific lib.)
http://www.gnu.org/software/gsl/manual/html_node/Fast-Fourier-Transforms.html

If you are doing polynominals, you are very likely to need the complex form, and depending on exactly how you set it up the 2D form of that.

However, you should also look at FFTW3 http://www.fftw.org/ which is faster but slightly more complex to set up, it current supports a host of chip features which really helps. It is straighforward to do 2D etc. It handles the case of non-radix2 FFTs etc much better than GSL. [Note: This is possibly because I have taken more time to figure out FFTW3 than GSL and the last statement just shows my ignorance. :-( ]

Both of these are in C, but they are easy to wrap. To get really good low-level access you are going to need to write complex methods and at that point you library can be in any language you like, just add the data entry/exit parts, into a class.

If you get stuck post some code, I am sure many here use GSL and FFTW3.

[Peter_APIIT]

As you know, i really a beginner in numerical analysis.

Well the basic FFTs are available in the GSL (gnu-scientific lib.)
http://www.gnu.org/software/gsl/manu...ransforms.html

If you are doing polynominals, you are very likely to need the complex form, and depending on exactly how you set it up the 2D form of that.

What you mean by 2d form ? Is GSL using colley_turkey FFT or other variation ?

What is radix and non-radix2 ?

Thanks.

[StuXYZ]

Yes the GSL algorithms provide a colley-tukey FFT but as you know, this is requires the data set to be expanded to fit [tex]2^N[/tex] points. This is fine for short data sets but not ok, for longer data set or were a specific transform basis is required.

There exist a number of other transforms that work better in different radixs e.g 2,3,5, and 7. These are also in the GSL.

In addition there is Singleton's method for arbitary radix. Note that this is slow. [tex]O(N^2)[/tex]

FFTW provides an arbitary size transform at [tex]O(N log N)[/tex] which is obviously a great advantage for large N.

2D transforms

A higher dimensional transform of an array is in effect a transform of a 1D array with different/mixed stride. There are some tidy ways to process that. They come about in polynomial systems as you introduce more variables.

There are two ways of approaching FFTs. (a) number theory, very interesting but takes a lot of time to get to the working solution.
(b) knowing that you need an Fourier transform and using the libraries as black boxes. (well sort of).

The libraries referenced above will give you (b) and a lot of other stuff will give you (a). If you go down (b) then ensure that you always check solutions for numerical stability, normalization and profile your code.

Note: It is colley-tukey. [but look both up on the web] since it was John Tukey who was co-author of the algorithm.

[Peter_APIIT]

What algorithm used by FFTW ?

[StuXYZ]

Your first followup question is explained on the page that you get by clicking on the first link I originally gave, the second, guess what it is explained on the page for the second, however, it isn't actually on the page I specified, you see there is a like called documentation.... :-O

Time to do the research that moves you from beginner to something else.

So if you look at the page you will see you need to read
Proceedings of the IEEE 93 (2), 216–231 (2005). Invited paper, Special Issue on Program Generation, Optimization, and Platform Adaptation. They kindly provide a pre-print.

Please read that then come back and ask about what you don't understand.