FFTW is the fastest FFT library. But its interface is in C. I'm wondering if there is any ongoing project on FFT.
You could try VSIPL++ at www.codesourcery.com
If I'm correct, VSIPL is not free, right?
As others have pointed out, VSIPL++ is 'as free' as FFTW. Both require a commercial license if used in closed source apps. Also note that Linux versions of Intel libs have an 'open' binary version but do check licenses. Also note that I don't think you have to have libraries like MKL/IPP or Mercury SAL (or ATLAS etc) but each may help you get better performance on a particular platform than the vectorised basic code your compiler might provide using VSIPL++ core without the libs. Really depends what you want to do. VSIPL++ was IMHO the best of the options I looked at for signal processing ~ 1 year ago though I'd characterise it as 'evolving' and not as mature as say Intel's MKL/IPP and equivalents.