Clean up some wording in the fft extension

[asmeurer]

Fixes #717.

I also plan to fix https://github.com/data-apis/array-api/issues/718 here.

Note: this should also be backported, but I want to make sure the wording here looks good first before I do that.

Also, I haven't done it here, but we should consider whether we want to add a dtype argument to fftfreq and rfftfreq for consistency with the other creation functions. Right now, they return the default real floating-point dtype, but there's no way to change that. However, note that np.fft does not implement a dtype argument for these functions.

Ref: https://github.com/data-apis/array-api/pull/189

[asmeurer]

"trimmed to length n" also isn't very clear. Does this mean it should take the first n elements?

[asmeurer]

I've also pushed an update to specify output lengths. Please check carefully.

I've also tried to clean up the wording a bit. However, I'm not sure if my wording here is always consistent with wording elsewhere in the spec, so let me know if something should be changed.

I noticed that we aren't consistent throughout the spec with "length" vs. "size" to refer to the size of an axis.

[rgommers]

Okay, this took a bit of digging, but I believe that @leofang is largely correct. The current state of the fft docs is inconsistent, and has been in that state since the initial merge of gh-189. The problem is that the Parameters section says that the first input x must have a "floating-point dtype" (so may be real), while the prominent note right above it says:

"Applying the one-dimensional inverse discrete Fourier transform to the output of this function must return the original (i.e., non-transformed) input array within numerical accuracy (i.e., ifft(fft(x)) == x), provided that the transform and inverse transform are performed with the same arguments (length, axis, and normalization mode)."

Clearly that is not the case if x would be real, because the roundtripping changes the dtype from real to complex (e.g., float64 to complex128). Hence real input should be rejected.

So far the spec - let's update the wording to reflect that. For implementations:

• The reference implementation should raise on non-complex input dtypes to fft/fftn.
• For NumPy 2.0, that'd be one bridge too far I think, so let's open an issue first - there are more issues with numpy.fft that need addressing. Accepting non-complex input and treating it like complex with a zero imaginary component will simply be one oddity that perhaps can be addressed over time.

[asmeurer]

Would we want to backport this to 2022.12, or just add it to the draft?

[asmeurer]

I've pushed a change that updates these functions to only require complex-valued inputs. I think this will also require a changelog entry, but I didn't add it yet because I don't know if it will be part of 2023.12 only or backported.

This PR also requires some review for other the wording changes that have been made, as discussed above.

[kgryte]

IMO, I think it is a bug in the 2022.12 revision and should be backported. For the changelog entry, we can add that in a subsequent PR along with the other specification changes which should be documented similarly.

[rgommers]

These changes all LGTM. I think if they are backported and added to the Changelog, this is good to merge.

[leofang]

Sorry I dropped the ball here. I think the PR looks good now from a quick glance. I can do a more thorough look tomorrow, but don't let me stop the progress 🙂 Thanks Aaron and all for the improvement!

[asmeurer]

I've backported everything to 2022.12. I've left out the changelog based on https://github.com/data-apis/array-api/pull/720#issuecomment-1884048884.

[asmeurer]

Found two more places where the specified output shape didn't match the numpy docs/implementation (rfft and rfftn). Need someone to confirm that the spec really should be changed here to match what NumPy does. Note that technically, the spec doesn't currently say what the output shape for those functions should be at all.

[asmeurer]

The spec for irfft says

Applying the one-dimensional inverse discrete Fourier transform for real-valued input to the output of this function must return the original (i.e., non-transformed) input array within numerical accuracy (i.e., irfft(rfft(x)) == x), provided that the transform and inverse transform are performed with the same arguments (axis and normalization mode) and consistent length.

But the NumPy docs say

In other words, irfft(rfft(a), len(a)) == a to within numerical accuracy. (See Notes below for why len(a) is necessary here.)

See the "notes" section at https://numpy.org/doc/stable/reference/generated/numpy.fft.irfft.html

I don't know if this caveat applies to other functions here as well.

(as an aside, is it intentional that n is not allowed to be positional in fft functions?)

[asmeurer]

Another one: NumPy 2.0 has a new deprecation warning if axes is None and s is not None:

>>> np.fft.irfftn(np.asarray([0.+0.j, 0.+0.j]), s=(1,), axes=None)
<stdin>:1: DeprecationWarning: `axes` should not be `None` if `s` is not `None` (Deprecated in NumPy 2.0). In a future version of NumPy, this will raise an error and `s[i]` will correspond to the size along the transformed axis specified by `axes[i]`. To retain current behaviour, pass a sequence [0, ..., k-1] to `axes` for an array of dimension k.

The spec doesn't seem to disallow this.

[asmeurer]

(as an aside, is it intentional that n is not allowed to be positional in fft functions?)

I didn't see any discussion of this in https://github.com/data-apis/array-api/pull/189 or https://github.com/data-apis/array-api/issues/159.

Just based on a cursory GitHub code search, it seems like passing n as positional is common. See also https://github.com/data-apis/python-record-api/blob/master/data/typing/numpy.fft.py (does that data distinguish between when an argument is passed positionally or as a keyword?).

With that being said, I'm haven't used the fft APIs so I can't say myself whether n being positional is something we should aim for or not.

I also want to clarify that I don't think this is an issue for NumPy either way. Right now NumPy defines n as a positional argument, but there's not really an incompatibility with doing so when the standard says keyword-only (at least in my opinion).

[asmeurer]

@leofang do you have any comments on my suggestions in my most recent comments? If there are no objections, I can update the spec accordingly.

[leofang]

For this question

The spec for irfft says

Applying the one-dimensional inverse discrete Fourier transform for real-valued input to the output of this function must return the original (i.e., non-transformed) input array within numerical accuracy (i.e., irfft(rfft(x)) == x), provided that the transform and inverse transform are performed with the same arguments (axis and normalization mode) and consistent length.

But the NumPy docs say

In other words, irfft(rfft(a), len(a)) == a to within numerical accuracy. (See Notes below for why len(a) is necessary here.)

See the "notes" section at https://numpy.org/doc/stable/reference/generated/numpy.fft.irfft.html

I don't know if this caveat applies to other functions here as well.

I think we were being sloppy back then, as the idea of performing round-trip transforms to get back the original data was clear, but a lot of caveats need to be handled carefully such as s and n choices. I didn't think I could come up with a concise expression to describe it accurately enough. If anyone has suggestion, please help phrase it better...

(as an aside, is it intentional that n is not allowed to be positional in fft functions?)

I prefer making it kw-only, but no strong opinion.

[leofang]

Another one: NumPy 2.0 has a new deprecation warning if axes is None and s is not None:

>>> np.fft.irfftn(np.asarray([0.+0.j, 0.+0.j]), s=(1,), axes=None)
<stdin>:1: DeprecationWarning: `axes` should not be `None` if `s` is not `None` (Deprecated in NumPy 2.0). In a future version of NumPy, this will raise an error and `s[i]` will correspond to the size along the transformed axis specified by `axes[i]`. To retain current behaviour, pass a sequence [0, ..., k-1] to `axes` for an array of dimension k.

The spec doesn't seem to disallow this.

We did say "If s is not None, axes must not be None either." Do I misread your question Aaron? https://github.com/data-apis/array-api/blob/95332bb71159cea68e15e7d20364a3e07060a402/src/array_api_stubs/_draft/fft.py#L425 The idea was when s is given we also need axes to disambiguate.

[leofang]

@leofang do you have any comments on my suggestions in my most recent comments? If there are no objections, I can update the spec accordingly.

@asmeurer so sorry for my unexpected delay 🙇 I just left some comments. Yes, please go ahead and fix them, and ping me for re-review when you're done. During an internal discussion it came to my attention that we need to make the output shape of C2R (i.e. irfft, irfftn) clearer too. I made suggestions above.

[asmeurer]

I think we were being sloppy back then, as the idea of performing round-trip transforms to get back the original data was clear, but a lot of caveats need to be handled carefully such as s and n choices. I didn't think I could come up with a concise expression to describe it accurately enough. If anyone has suggestion, please help phrase it better...

Actually, I didn't notice it already caveats this in the text:

Applying the one-dimensional inverse discrete Fourier transform for real-valued input to the output of this function must return the original (i.e., non-transformed) input array within numerical accuracy (i.e., irfft(rfft(x)) == x), provided that the transform and inverse transform are performed with the same arguments (axis and normalization mode) and consistent length.

(emphasis mine)

So I think we don't need to change anything here.

[asmeurer]

We did say "If s is not None, axes must not be None either." Do I misread your question Aaron?

It looks like you're right. I must have missed this text previously.

[asmeurer]

Also noticed another issue, quite a few of the type hints do not properly use Optional for arguments that could be None.

[asmeurer]

@leofang I just pushed a commit with the proposed fixes. If you could review the text and make sure it is both correct and sufficiently unambiguous, that would help. I'm particularly not sure about the best way to word things with the s given that there are so many conditions (s could be None or s[i] could be -1).

I have only updated _draft for now. Once we agree with the changes I will backport all changes to _2022_12.

[asmeurer]

One final (hopefully) thing which I have not done here is adding a dtype argument to the fft creation fucntions fftfreq and rfftfreq. This would be an actual API change, and one for which NumPy is not currently compatible (although torch is). So if we want to make this change it should not be backported. Perhaps it would be best to do this only for the 2024 spec, given that it hasn't actually been requested by anyone yet, and we are close to tagging 2023. I will open a new issue about this.

[asmeurer]

Actually https://github.com/data-apis/array-api/issues/717 can already be the issue for this.

[asmeurer]

@kgryte could also use your review here to make sure the wording looks good everywhere. I modified quite a few sentences to make them less ambiguous. Again, please only look at _draft for now. I will backport everything to _2022_12 once it all looks good.

[leofang]

I am reviewing now

[leofang]

@asmeurer @kgryte I could use extra pairs of eyes 🥺

btw I've synced 2022 and the draft versions (simple copy/paste)

[kgryte]

@leofang Of course. Will take a look tonight.

[leofang]

I'm particularly not sure about the best way to word things with the s given that there are so many conditions (s could be None or s[i] could be -1).

In commit a84c293 I tried to separate out the None case, as it could be a bit nasty especially with irfftn.

[leofang]

btw I dunno if it's a me problem, but every PR that I touched (this one and others) failed in the CI/CD...

[kgryte]

@leofang An unlucky touch? 😅 I'll make a note to investigate once we get these in.

[kgryte]

@leofang Looking at the CI logs, looks like you need to locally install dev deps in order to run the pre-commit hook which will apply black formatting before pushing.

[kgryte]

I think we are good to go ahead and merge this in. Any additional tweaks can be addressed in follow-on PRs.

Thanks, @asmeurer and @leofang!

[leofang]

@kgryte thanks, I'll check again later today. One thing I noticed: the diff contains a lot of non-FFT-related changes, is this expected?

[kgryte]

@leofang GitHub seems confused. The actual diff only includes FFT changes. See https://github.com/data-apis/array-api/commit/937d3b8e22ef42d2420a951cefe6ec28107f31bf.

[leofang]

Interesting, I thought only Gitlab would be confused not GitHub 😀 We squash-merged, right?

[kgryte]

We squash-merged, right?

Yes, we did. 😀

[leofang]

Thanks for all the editing, Aaron/Athan. Looks nice! I sent a tiny follow-up: #743