Managed Fourier.Radix2Inverse speed up

[xmedeko]

Hi, I do not know FFT in depth. I just need a fast, open source inverse FFT implementation. I have tested 3 implementations:

1. Math.NET Fourier.Radix2Inverse : the slowest for the small data (1024 and lower), fastest for the large data (i.e. 10^6).
2. LomontFFT:

• Plain FFT, faster than Math.NET for small data.
• TableFFT with coefficient caching. Small perfomance benefit for small data (64 and lower) when the object is reused many times. For large data it's slower then plain FFT even when the object is reused.

3. Gerry Beauregard's FFT: it uses linked list. Surprisingly, it is the fastest implementation for the small data when the time for the linked list initialization is not counted. (Apparently C# has faster linked list access than array.) Drawback is the memory consumption for the linked list for large data.

I think Math.NET good performance for large data is due to the exploited parallelism. So I think it could be further speed up maybe by using Chris Lomont's FFT.

Note: I have not tried Iridium FFT. I have just peeked into it's code and seen that is uses coefficient caching in an array. With my experience from LomontFFT.TableFFT the coefficient caching does not bring any performance benefits.

[cdrnet]

Thanks for the input!

Which version are you using? I have recently spent some time in this area, mainly on adding native provider support (MKL for now, but I'd like to add FFTW) but have also slightly altered the managed implementation based on benchmarks (3.14.0-beta01). I have similar conclusions so far for our current managed implementation, with the addition that there seems to be an issue on x86 JIT (significantly slower than x64 with RyuJIT).

[xmedeko]

Hi, I've use 3.14.0-beta03 on the 32-bit OS, .NET 4.5, CPU Intel i5, 2.5Ghz, 2 cores, 4 logical CPUs.

I have run a few tests just LomontFFT vs Math.NET again and see that they are roughly similar for the small data (param Complex[] spectrum) 32, 64, ...,. Then, the Math.NET starts to be relatively slower, so as for the length 512 is the LomontFFT apparently faster (approx 40%). For the high data length the Math.NET is again the first.

So, I reject my assumption in the first post. Now, it seems to me the core algorithm of the Math.NET is similar to the LomontFFT (for my environment), just the parallelization starts to early?

BTW. the FourierOptions is the enum. I would generally recommend you to use a general object instead of enums as the algorithms options, since it may contain more properties, like ParallelizationStart, etc.