Include FFT

[certik]

We can use FFTPACK, or my own modern Fortran refactoring of it: https://github.com/certik/hfsolver/blob/b4c50c1979fb7e468b1852b144ba756f5a51788d/src/fourier.f90 and we need to allow optionally using MKL or FFTW.

NumPy uses FFTPACK that they transformed into C and heavily modified: https://github.com/numpy/numpy/tree/a9bb517554004cf2ce7a4be93bcbfb63ee149844/numpy/fft. We could use it also, but I think it might be valuable to stay in Fortran (see #20).

[rweed]

Be careful with MKL. I don't know about FFT etc. but I encountered a problem with their implementation of LAPACK90 where they changed the argument list (same arguments but in different order) on some of the subroutines. Not a problem if you know about it before hand and use the keyword arguments but you would hope that Intel would have had the good sense to keep the netlib LAPACK90 interfaces as is.

[leonfoks]

@certik At the top of your fourier.f90 you mention that its an O(n^2) code? Or is that just for the dft and idft subs? Isn't the Cooley Tukey algorithm O(nlogn)?

[certik]

@leonfoks yes, the dft is slow O(n^2), and the fft_pass is the fast O(n*log(n)) FFTPACK algorithm. I think I have an improved API in my internal code that is not open source.

In the stdlib, there should just be a function fft that works in 1D, 2D, 3D and that uses the FFTPACK version.

[zoziha]

The FFTpack library on netlib seems to have only double precision and only one-dimensional FFT. netlib/fftpack

There is a more complete and updated fftpack, including 1-dimensional, 2-dimensional, and multi-dimensional real and complex FFTs🎈. FFTPACK 5.1 - A Fortran77 library of fast Fourier transforms

There is a nice library based on fftpack on github, which contains some customized functions, such as fftshift, ifftshift, which is very cool🥰, contains a "forlab" module. keurfonluu/FFTPack

Forlab is a Fortran module that provides a lot of functions for scientific computing mostly inspired by Matlab and Python's package NumPy. keurfonluu/Forlab

Because of the changes in gfortran10 compilation options, compiling fftpack may require fflag --fallow-argument-mismatch (see https://github.com/keurfonluu/FFTPack/issues/1).

Thank you! Hope that the Fortran ecology will get better and better~🎉🎉

[hsnyder]

@certik based on reading fortran-lang/fpm-registry#40 it sounds like the current plan is to maintain fftpack under fortran-lang, as it's own library rather than fold it into stdlib, is that correct? If so, I'm curious as to why we don't simply include it in stdlib?

[certik]

@hsnyder sorry, I forgot to reply. We can of course just include it in stdlib, but I think it's better to maintain it as a separate standalone package, and just make stdlib depend on it. We can then include modern Fortran interface, either in stdlib, or in the fftpack standalone package. It seems that's a better decision, because I think there will be interest in having a well maintained standalone package for all these old libraries like fftpack.

[bkmgit]

Would FFTE also be considered? Or a translation of KISS FFT to Fortran?