On 05/28/2013 06:12 PM, Nathan Bliss wrote:
Dear Boost Community Members, I am writing to ask if I could contribute a C++ FFT implementation to the boost library. I noticed that there is a boost::CRC so I thought it would be a good addition to have boost::FFT as well. MIT have an existing open-source FFTW library, but it is GPL-licensed which is much more restrictive than the Boost license. I should imagine a commercial FFTW license would be very expensive.
I certainly don't speak for the Boost community at large, but in my opinion, an FFT library would be a great addition to Boost. While for performance-critical applications, I doubt you would be able to approach the speed of a specially-tuned implementation like Intel's Math Kernel Library, a portable, parallel-capable, easy-to-use, freely licensed library that provides decent throughput would be useful. Some thoughts that come to mind: - Do you have any benchmark information available? A comparison to contemporary competitors like FFTW, Intel's MKL on x86 platforms, or kissfft (http://kissfft.sourceforge.net/) would be useful. - The 6e-6 relative error specification that you quoted (when compared to FFTW) seems a bit large to me for double precision. Have you characterized what causes the difference? - You might already support some of these, and I've not been involved in Boost development myself, but from observing the process, I would guess that an FFT library would need to provide a lot of flexibility in order to be accepted. Some of the features that I would consider important would be: - The ability to compute both forward and inverse FFTs - Optimized forms for real inputs (i.e. only computing the half spectrum due to the conjugate symmetry in the result) or real outputs (i.e. calculating the inverse FFT on a half spectrum that is assumed to be conjugate symmetric) - An interface to compute multiple transforms in a batch (which can improve throughput, especially for smaller transforms), maybe even customizable input and output strides and distances (like FFTW) - Multiple backend implementations to allow for non-power-of-2 transform sizes - One other idea that is somewhat pie-in-the-sky right now: FFT algorithms are a great fit for SIMD implementations, so perhaps support for the still-in-development Boost.SIMD library (http://nt2.metascale.fr/doc/html/the_boost_simd_library.html) would be a future possibility. Jason