Discussion : Generic interfaces for the Fourier transforms

[loiseaujc]

Hej everyone,

Given how far we've gone with the linear algebra module, I think it is time to think a bit about what could be the next "big" addition to stdlib. Following some old discussions (see #1, #20, #21, #66, #409 and #540), introducing fast Fourier transforms capabilities seem like the natural next step. Having access to the FFT (and its variants) would allow for numerous additional functionalities, including (but not limited to):

• signal processing: spectral analysis, convolution, auto-correlation, cross-correlation, etc.
• partial differential equations: spectral and pseudo-spectral solvers, fast elliptic (e.g. Poisson) solver, etc.
• linear algebra: circulant matrices, fast matrix-vector product for Toeplitz and Hankel matrices, etc.

There are many FFT libraries available out there, with different licenses and API. From reading the previous discussions, it seems to me that the consensus back then was something along the following lines:

• Have fftpack as a stand-alone package.
• Implement some high-level interfaces (e.g. y = fft(x), p = plan_fft(x)) in stdlib which would allow to switch between different backends (to alleviate licencing issues with FFTW for instance) with fftpack being the default one.
• Have wrappers for the most common backends, e.g. fftpack, FFTW, MKL, and possibly a couple of others.

Note that if fftpack is the default backend, we would need to keep the modernization effort started by @jacobwilliams in order to cover all the different precisions by stdlib.

@certik, @milancurcic, @ivan-pi : is my understanding of the discussions you had a couple of years ago correct ? Do you still stand by this point of view or has it evolved?
@perazz, @jvdp1, @jalvesz : Given your experience with developing the linear algebra module, do you have insights that could be useful for the fft endeavor?

[jalvesz]

I'm not familiar with FFTW or the MKL APIs for FFT, but my understanding is that MKL actually proposes a drop-in replacement with the same API signature. So I guess that a similar approach to what was done for BLAS/LAPACK can be done here: integrate fftpack within stdlib as the default backend and have a C-preprocessing macro with something like STDLIB_EXTERNAL_FFT to link against precompiled-optimized versions (FFTW or MKL).