Generative Fast Fourier Transforms (GFFT)
0.3
|
The main feature of GFFT library is that the length of transform is defined as a compile-time constant. You may compile FFT of only single length or easily define and compile a set of transforms, e.g. the powers of 2 from 1 to 25 or a range 10,...,20, etc.
The major advantage is that the first and expensive planning step usually performed by the known FFT libraries is fully done at compile-time. Even the twiddle factors are partially computed during compilation. Knowing the length of transform, the compiler can orginize and optimize the code better. As result, at run-time GFFT performs the transform in one step avoiding expensive planning.
GFFT is a header-only library with a couple of sample programs and some files from Loki-lib library by Andrei Alexandrescu. It doesn't need any installation or additional packages.
Starting with version 0.2 GFFT has cmake-based build management. That means, you can take a look and make changes in CMakeList.txt file, where all the compiler options and targets are listed.
To compile the project, run cmake in GFFT directory, then run make:
cmake . make
Compilation of GFFT is compiler-challenging process, because it intensively applies template class recursion, which must be completely resolved during compilation. For instance, it is known that gcc 3.x hangs up, when trying to compile GFFT in optimized mode. Newer compilers can handle template classes much better and faster. GFFT 0.3 is succesfully tested with
Other compilers will be tested soon.
The compilation should take from a few seconds to a few minutes depending on amount of transforms you would like to compile within your code.
To start using GFFT please take a look into simple example programs (gfft*.cpp and cgfft*.cpp). The first one defines the data as a C-like array, where each even element represents the real and odd - the imaginary part of a complex number. The second one uses array of std::complex type.
Since all the parameters of GFFT are static constants and defined as template parameters, you have to deside before compilation, which kind of transforms of which length you might need and declare them in instantiation of template class GFFT::GenerateTransform (see its documentation for details). Its template parameters may be given as a single type or as a typelist with multiple options.
An object of this instantiated template class contains then object factory of all the needed transforms. Each of them can be obtained from the object factory on demand. Following example declares forward and backward complex transform of double precision in single-threaded mode and creates a transform object for forward transform of length 2^10:
If you need only single transform type of fixed length, then you can use directly template class GFFT::Transform without object factory.