Add FFT extension to the spec

[steff456]

This PR focuses on adding the FFT as an extension to the array spec.

The current APIs added in this PR are:

• [x] Standard FFT: fft, ifft, fftn, ifftn
• [x] Real FFT: rfft, irfft, rfftn, irfftn
• [x] Hermitian FFT: hfft, ihfft
• [x] Helper Routines: fftfreq, rfftfreq, fftshift, ifftshift
• [x] Update to rst and create function stubs

They follow the summary available at #159

[steff456]

@leofang I already made the changes, please let me know if there's something else we can improve here :)

[rgommers]

Are we ready to merge this now, or is there more to do? The complex number support is available now.

[kgryte]

@rgommers I'll do a final pass through. Everything should be more or less complete. I can merge after.

[steff456]

@kgryte let me know if I need to do any changes regarding the types of the docs, @rgommers I will also review to see if there's something that needs to be tweaked for this PR

[steff456]

I already made,

• A general revision round
• Merged with master to have the latest changes including the rename of the main folder
• Addressed the last comment that depended on the complex number support

Let me know if there's something else that I need to fix but I think this is almost ready 🎉

[steff456]

I already did the changes with your last review, so just for recap this is the state of inputs/outputs for each function:

Name	Input	Output
fft	real & complex floating-point	complex floating-point
ifft	real & complex floating-point	complex floating-point
fftn	real & complex floating-point	complex floating-point
ifftn	real & complex floating-point	complex floating-point
rfft	real floating-point	complex floating-point
irfft	complex floating-point	real floating-point
rfftn	real floating-point	complex floating-point
irfftn	complex floating-point	real floating-point
hfft	real floating-point	real floating-point
ihfft	real floating-point	real floating-point

Let me know if there's something wrong in this table :)!

[leofang]

I'll try to take another look before Thursday, sorry a bit swamped...

[kgryte]

@steff456 The table looks correct. Thanks for putting that together.

[leofang]

Another note: As discussed in a prior meeting it is preferable to add a note that the output dtype will be consistent with the input dtype (ex: we don't always promote to complex128 as NumPy currently does even if the input is in single precision), but I think if we word it correctly when addressing #478 this need should be automatically resolved.

[leofang]

Hi @steff456 Do you have local changes that you have not pushed? If not, may I edit in your branch directly?

[steff456]

Hi @leofang, go ahead and make changes! Thanks a lot 😬

[leofang]

@kgryte @rgommers @peterbell10 @toslunar @steff456 @oleksandr-pavlyk This should be ready now. Any chance any of you can take a look? Otherwise, I'll self-merge before the next Array API meeting (Oct 20).

[rgommers]

Thanks @leofang! I had a quick browse, it looks like it is in good shape. I'll defer to @kgryte for a last in-depth look if he wants to.

[leofang]

Announced in the meeting, let's merge. We can follow up with additional PRs if needed.