Support (I)FFT calculations

[Jolanrensen]

For my specific data engineering application, having a fast Fast Fourier Transform algorithm would be great to have. However, there are many applications that could benefit from FFT, like audio analysis.

Most math/vector libraries have some form of (inverse) FFT built in, like Numpy for Python, Apache Commons for Java (which is slow) or JTransforms (which is quite fast and multi threaded but doesn't use SIMD).

I think FFT could benefit a lot from the SIMD capabilities of Viktor.

This is confirmed by some papers of which this is just the first example I could find.

Intel MKL also has a form of FFT built in which uses SIMD (and maybe other Intel stuff) as well.

I don't know if boost SIMD already has FFT built in, but I wouldn't be surprised if it does.

[dievsky]

Thank you for your interest! I will look into it. I didn't find any FFT methods in boost.SIMD, unfortunately.
Do you have some specific FFT variety in mind? AFAIR, there are some special cases for different array sizes, like for powers of two, for other composite numbers, for arbitrary numbers etc.

[daphil19]

I'm coming at this fairly naively, but would wrapping fftw with JNI calls may be an effective way to implement this? The fallback for unsupported architectures could be JTransforms.

[dievsky]

It might be effective, but it would also require either re-licensing viktor or purchasing a dedicated fftw license, since fftw is apparently GPL.

[Jolanrensen]

Thank you for your interest! I will look into it. I didn't find any FFT methods in boost.SIMD, unfortunately.
Do you have some specific FFT variety in mind? AFAIR, there are some special cases for different array sizes, like for powers of two, for other composite numbers, for arbitrary numbers etc.

Powers of 2 are fine. I understand they are more efficient that way (and Apache Commons also had this as a hard limitation). Other than that, here is what I specifically am using right now:

A forward Fast Fourier Transform using a real double array as input which outputs a complex array (in the form of [real0, complex0, real1, complex1...]).

I perform a multiplication of two of these "complex" arrays.

I perform an inverse Fast Fourier Transform with scaling on this complex array and from that result I take just the reals.

It might be possible to still wrap another library that uses SIMD. I'm currently trying to get Intel MKL to work for my project, but I can't get the linking to work in Gradle, however there are many libraries: https://github.com/project-gemmi/benchmarking-fft

[dievsky]

A couple insights:

• MKL seems to be the most versatile, but it's also big, Intel-oriented, and closed-source;
• PocketFFT is lightweight, but only does SIMD for multidimensional arrays.

We could also probably implement a SIMD-friendly decimation-in-frequency reduction ourselves, delegating the actual FFT for small arrays to Apache Commons Math (we have it as a dependency anyway).

[Jolanrensen]

A couple insights:

• MKL seems to be the most versatile, but it's also big, Intel-oriented, and closed-source;
• PocketFFT is lightweight, but only does SIMD for multidimensional arrays.

We could also probably implement a SIMD-friendly decimation-in-frequency reduction ourselves, delegating the actual FFT for small arrays to Apache Commons Math (we have it as a dependency anyway).

I'd skip Apache Commons actually. It converts its results to Complex class instances and when I rewrote it to use F64FlatArrays, compared to JTransforms, it was just very slow.

I did find another list of libraries: https://community.vcvrack.com/t/complete-list-of-c-c-fft-libraries/9153

[dievsky]

OK, thanks for the info! It's surprisingly hard to find a permissive-licensed library doing 1-D SIMD on doubles on this list, so the option of combining the existing SIMD capabilities with a Java FFT implementation is still viable.

[dievsky]

After some research, it looks doubtful that we'll be able to perform the decimation using existing SIMD capabilities, The problem is that we require complex multiplication for this, and all the libraries I've seen expect the complex data in interleaved format (RIRI), while SIMD would only work well with split format (RRII).

[Jolanrensen]

After some research, it looks doubtful that we'll be able to perform the decimation using existing SIMD capabilities, The problem is that we require complex multiplication for this, and all the libraries I've seen expect the complex data in interleaved format (RIRI), while SIMD would only work well with split format (RRII).

However many of the libraries, like Pffft already do use SIMD, so that should be plug-and-play right? It's only "pretty" fast though, but it does use SIMD, so I guess that would make it at least "quite" fast, haha.

[dievsky]

Yes, the previous comment was related to the option where we would decimate in Kotlin using viktor's existing SIMD capabilities and delegate to JTransforms once the array size became small enough.

[dievsky]

pffft only works with floats, unfortunately. PocketFFT only uses SIMD for 2+ dimensional arrays. FFTW is under GPL.

[Jolanrensen]

I see, you're right. Maybe we can convert pffft to doubles? Not sure how this would affect the program (but I don't consider myself an active low-level programmer anyways, so I might be wrong).

[Jolanrensen]

Oh here we go, with double support: https://github.com/marton78/pffft