Shift to a non-GPL library for FFT/DCT computation
Created by: laurentes
Bob (1.2.x) currently relies on FFTW for FFT/DCT computation. FFTW has a GPL license. We are now considering to turn the license of Bob from GPL to BSD. This would imply that we should not link any more against GPL libraries. FFTW is the only GPL dependence that we have.
Furthermore, we are looking for alternatives to FFTW. There are already naive implementations of DFT/DCT in bob, which are used for testing purposes. But there are really slow for large arrays. We are hence looking for more optimized source code. I have performed few tests to rely on two different BSD-like FFT libraries:
Kiss FFT (C and C++ implementation): I was not able to make the C implementation working with 'double' instead of default 'float'. This just provides wrong outputs. And the documentation is quite poor. The C++ implementation is working with 'double', but it does only support 1D FFT (No nD FFT or DCT computation). However, I still had to tweak/fix the code to make it compatible with all the platforms we are supporting.
NumPy's FFT implementation (C code based on former FFTPACK fortran's implementation [P.S.: Note that SciPy also provides a different FFT implementation based on the original FFTPACK fortran's code]:. NumPy's implementation only provide FFT (not DCT). The code is much larger than the one of kiss FFT (2k lines vs 200 lines), but is probably more reliable, since it has been used for several years by this wide deployed library.
For both solutions, we won't add a new dependence, but instead we would just cannibalize the FFT source code into bob central repository (There is no Ubuntu/OS X packages for kiss FFT any way). I have pushed FFT/DCT implementations in the master branch that rely on both libraries (separately), to keep track of all the tests I did. Solution 2. is my favourite so far. If we go for it, I will just remove the FFTW and kiss FFT-based implementations, and renamed the FFT1DNumpy (2D/DCT, etc.) classes into FFT1D. The documentation should then be carefully updated. As the underlying implementation's will be different, this may slightly affect the outputs/features/results generated with FFTW.