Re: [boost] Request to contribute boost::FFT

Subject: Re: [boost] Request to contribute boost::FFT
From: Jason Roehm (jasonr_at_[hidden])
Date: 2013-05-28 22:51:06

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