Numpy FFT implementation?

[vade]

Hi there

Firstly, this library looks amazing. You've done a ton of work and it looks really promising. Thank you!

I was curious if there was any plans to implement Numpy's FFTs in vDSP? If not, do you do work for hire?

I did some work looking into this myself for work on porting OpenAI's Whisper to CoreML / Accelerate https://github.com/vade/OpenAI-Whisper-CoreML

And I documented some of my findings in this issue here: vade/OpenAI-Whisper-CoreML#1

It seems like Numpy, PyTorch, Rosa / RosaKit all use PocketFFT to do non power of 2 DFTs, which is why the output matches more or less exactly numerically.

PocketFFT doesn't use vDSP, but rather scalar - no simd acceleration.

Given the rest of MatFT's current implementation, doing the STFT and Log Mel work in MatFT would just work. The only missing piece is a numerically equivalent implementation of the Numpy / Torch 'real to complex' (rfft) logic.

Thank you again for all the work on Mattft!

[jjjkkkjjj]

@vade
Thank you for your feedback!

I have no plans to implement FFT for now, but maybe I can implement numpy's FFT to use some vDSP_* functions such like vDSP_DFT_Execute or vDSP_fft_zrip as you mentioned your issue.
And then, because the fft's output is complex, I must implement some ToDo.

do you do work for hire?

What do you mean? I'm not good at English... lol

[vade]

Hi. We're (my company) is looking at using Matft library for usage in our product. We might want to sponsor some features, ie: pay you to do some work on Matft for the community under the same BSD license, so everyone can benefit and can be shared by all.

Some things that could be awesome:

• MLShapedArray support - ie effortlessly use an MLShapedArray with Matft
• FFT support to some degree (we only care about forward real ftt for now)
• im sure there will be more here !

It would be really good for the Swift / ML / Ai / Computer Vision community to have a native, fast library similar to functionality to Numpy !

[jjjkkkjjj]

Really!?
I’m very welcome to sponsor Matft!! I’m getting motivated 🫡
Should I open a GitHub sponsor?

Anyway, I’ll try to implement some features you mentioned!

• Support MLShapedArray
  • Share memory (If possible )
    • Matft will be able to use the same memory in MLShapedArray by withUnsafeMutableShapedBufferPointer
  • Copy memory
• Implement FFT
  • numpy.fft.rfft
  • numpy.fft.fft (If possible )
• Finish some tasks for complex (Complex support #24)

[vade]

Hah! Glad you're feeling motivated. Before we all get carried away its helpful to align and set some expectations. I'll send you an email to the address on your git account. Look for an email from anton [at] :)

Thanks!

[jjjkkkjjj]

Look for an email from anton [at] :)

OK!

Notice:
I couldn't initialize MLShapedArray. So, I've supported MLMultiArray instead :( (#40)

[jjjkkkjjj]

numpy implementation code
https://github.com/numpy/numpy/blob/main/numpy/fft/_pocketfft.py

[jjjkkkjjj]

I've just implemented rfft.
But its result was different from numpy

let a = MfArray([0, 1, 0, 0])
let real = MfArray([ 1,  0, -1])
 let imag = MfArray([ 0,  -1, 0])
            
XCTAssertEqual(Matft.fft.rfft(a), MfArray(real: real, imag: imag, mftype: .Float))

XCTAssertEqual failed: ("mfarray =
[ 0.99999994 +0j, -0.99999994 +0j, 0.0 +0j], type=Float, shape=[3]") is not equal to ("mfarray =
[ 1.0 +0j, 0.0 -1j, -1.0 +0j], type=Float, shape=[3]")

Its optimization may be different from numpy's one.
Anyway, I'll try to incorporate pocketFFT (used by numpy) into Matft

[jjjkkkjjj]

@vade
I've just implemented rfft and irfft!! (also complex setter (#24))
Notice: I used pocketFFT used in numpy, so this function is not accelerated. I'll try to implement vDSP_fft_op to be faster.
Anyway, please check the latest fft branch!

[jjjkkkjjj]

Memo:
https://www.jstage.jst.go.jp/article/jasj/77/5/77_331/_pdf
It's very helpful to understand DFT.

https://tiny-wing.hatenablog.com/entry/2016/06/27/093809
According to vDSP programming guide, real and imaginary element in the first element of a returned complex are DC component and nyquist one respectively.

[jjjkkkjjj]

Because vDSP needs the exponent of 2 as an argument, it seems vDSP function cannot calculate odd frequencies?

[jjjkkkjjj]

I merged fft branch into master