search

psambit9791 / jdsp

A Java Library for Digital Signal Processing
https://jdsp.dev
MIT License
240 stars 45 forks source link

FFT Request Performance Enhancement #19

Closed RainbowZephyr closed 2 years ago

RainbowZephyr commented 2 years ago

Hello, Currently the performance of the Discrete Fourier in Java is sub-par, is it possible to integrate the FFTW if it is installed on the system to use it as it is backed by C? It runs in milliseconds compared to minutes on Java when running a 1 million point signal

Thanks in advance

psambit9791 commented 2 years ago

Looking into how this can be implemented.

psambit9791 commented 2 years ago

An initial search showed this to be a clean implementation of FFT done purely in Java. https://commons.apache.org/proper/commons-math/javadocs/api-3.4/org/apache/commons/math3/transform/FastFourierTransformer.html

Will incorporate this first to see if any time improvements are observed.

Testing will be conducted on the electrocardiogram() [ECG Signal] which has 108000 data points.

RainbowZephyr commented 2 years ago

Thank you so much for your time

SiboVG commented 2 years ago

I would very much second this; am developing an Android app that would use jDSP and the app is on the verge of crashing with the DFT of just a 1 second sample, sampled at 1 kHz...

psambit9791 commented 2 years ago

Using the FastFourierTransformer provided by Math3, these are the stats for executing long duration signals:

100000 points

FFT execution time in nanoseconds: 43335206 DFT execution time in nanoseconds: 574648468031 (~6 minutes)

1 million points

FFT execution time in nanoseconds: 154251513 DFT execution time in nanoseconds: ∞ (My patience just ran out!!!)

FFT improves execution time significantly

However, there seems to be a difference in the outputs apparently because FastFourierTransformer only accepts signal lengths in the power of 2. The resolution of the output is different between FFT and DFT.

SiboVG commented 2 years ago

However, there seems to be a difference in the outputs apparently because FastFourierTransformer only accepts signal lengths in the power of 2. The resolution of the output is different between FFT and DFT.

Yep, that's inherent to the FFT algorithm; it makes use mathematical tricks when the input is a power of 2...

psambit9791 commented 2 years ago

However, there seems to be a difference in the outputs apparently because FastFourierTransformer only accepts signal lengths in the power of 2. The resolution of the output is different between FFT and DFT.

Yep, that's inherent to the FFT algorithm; it makes use mathematical tricks when the input is a power of 2...

Yes. The FFT Butterfly needs the length to be a power of 2. Padding the DFT input gives the same output as FFT so the test works now.

psambit9791 commented 2 years ago

Completed implementing FastFourier and InverseFastFourier. The simple tests for FFT and I-FFT works so implementation is fine. Also modified the source codes for Hilbert, STFT and ISTFT to incorporate FastFourier classes. However, based on what I have tested, below 200 points, the DiscreteFourier is more time efficient. So I have created a conditions to choose which Fourier Method to use.

@SiboVG Could you write some test cases to test the modifications are functioning please?

SiboVG commented 2 years ago

@SiboVG Could you write some test cases to test the modifications are functioning please?

Just for the FFT and IFFT?

psambit9791 commented 2 years ago

Just for the FFT and IFFT?

Nope. Those tests have been passed. Additional tests for STFT and Inverse STFT. Present tests still use DFT and I-DFT because the signal lengths are fairly small.

I am writing tests for Hilbert Transform cases which uses FFT.

SiboVG commented 2 years ago

Alright, I'll take a look at it