ENH: Optimize the FFT implementation

Nobody has claimed this yet.

Fast Fourier transforms are widely used for applications in engineering, music, science, and mathematics.The current fft implementation was introduced two years ago(#11885, #11888 ), which is not the best implementation as far as I know, The drawbacks includes:

Don't supports single precision transforms.
Don't support for multi-D transforms.
Don't make use of vector instructions for FFTs, The main reason that It's performance is not good enough(At least better than fftpack).

Although the author published the C++ based pypocketfft later, which has overcame these shortcomings, but It's was not compatible with C based numpy, I found out that there has several backend projects that worth considering.

project	worth introducing?
fftw3	Most popular FFT library, which nowadays is the "gold standard" for FFT implementations. It's also the default fft algorithm of matlab, there has a python wrapper pyfftw, can't integrated due to it's GPL Licence.
Intel MKL/IPP	Significantly faster than FFTW with intel processors, already integrated as a third party lib.
KFR	Claims to be faster than FFTW, can't integrated due to it's commecial Licence.
FFTS	reported to be faster than FFTW because the use of SIMD instructions, at least in some cases. worth considering.
FFTE	reported to be faster than FFTW, but the source code is Fortran-based.
Ooura FFT	provide C and Fortran version implementation, but It hasn't been updated in a long time.
muFFT/pffft/PGFFT	have performance comparable to FFTW.depends strongly on the SIMD instructions. but with limited features.
KissFFT/PocketFFT	The simplest but also the slowest one here, which is the current solution.

Now we have two options:

choose a new backend system such as FFTS, which is painful because of the trival adaptation process.
optimize the current algorithm based on universal intrinsics, which is more practical and operable.

Start by reviewing NumPy's current FFT implementation and the history in issues #11885 and pull request #11888. Compare the proposed FFTS, pypocketfft, and universal-intrinsics approaches, including their licensing and support for single-precision and multidimensional transforms. Done requires an agreed backend or optimization plan with improved performance and the missing transform support.

Written by the indexing model from the issue text.

Description

Contributor guide

First steps

Research direction

Assessment