If you end up with an FFT implementation faster than numpy or pyFFTW then that would likely be useful to the OSS community as its own package!

I saw a rather new FFT implementation in Rust named PhastFT that you may find interesting as well. They have some benchmark plots on their Github readme which includes numpy. It looks like they have some python bindings but I'm unsure the effort involved to bring this into your project.

I'll definitely subscribe to the issue and follow along. Thanks!

If you end up with an FFT implementation faster than numpy or pyFFTW then that would likely be useful to the OSS community as its own package!

FFTW is certainly the gold standard and also why the DAMP implementation in Matlab is so performant. Of course, FFTW is known to have a ton of custom tweaks to make things fast and, since it's not our forte, we only aspire to come within 2x of FFTW (on average) while attempting to keep things "general". So, our goal is to implement an FFT that is "Fast Enough" while still being easy to maintain.

I saw a rather new FFT implementation in Rust named PhastFT that you may find interesting as well. They have some benchmark plots on their Github readme which includes numpy. It looks like they have some python bindings but I'm unsure the effort involved to bring this into your project.

I think we came across PhastFT as well. However, as a design philosophy, STUMPY has always opted to minimize our dependencies (we only depend on numpy, scipy, and numba) and this choice has served us well (for better or for worse). Of course, if our default "Fast Enough" implementation isn't good enough then @NimaSarajpoor and I have also discussed a simple design that will allow the user to specify their preferred FFT backend (e.g., PhastFT, PyFFTW, etc). That way, STUMPY is not on the hook for dealing with external dependencies. At the end of the day, all we need is to perform a (FFT) convolution so any fft/ifft pair will do.

Please stay tuned!

One more question for you on the FFT development in STUMPY: will you need a non-uniform implementation of the FFT to work with irregularly spaced time series or are you able to get around this somehow?

Technically, matrix profiles assume that all of the data is equally spaced. However, note that "time" is never actually used in any calculation and so "equal spacing" is assumed but not enforced/checked. Whenever STUMPY receive an array of numbers, we just blindly assume that the data is "correct". Thus, we only require the use of standard FFT algorithms.

To be clear, this is not a STUMPY issue and, instead, is what was described in the matrix profile papers