Implement n-d complex FFT

[wheeheee]

Done with only a little macro usage.

• mul! for arrays and plans of the same dimension is type-stable, but otherwise isn't.
• Planning will be less type-stable because the return type is not a small union, but it's unavoidable unless you drop the AbstractFFT interface
• Real FFTs look a bit trickier, so I'm a bit lazy to do them up
• 2D FFTs are probably a little faster now, only tested with 1024*1024 arrays though

[codecov]

Codecov Report

❌ Patch coverage is 99.41520% with 1 line in your changes missing coverage. Please review.
✅ Project coverage is 98.66%. Comparing base (bf2c0eb) to head (860e6f7).
⚠️ Report is 11 commits behind head on main.

Files with missing lines	Patch %	Lines
src/plan.jl	99.41%	1 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #109      +/-   ##
==========================================
+ Coverage   96.66%   98.66%   +2.00%     
==========================================
  Files           4        4              
  Lines         480      525      +45     
==========================================
+ Hits          464      518      +54     
+ Misses         16        7       -9     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[andreasnoack]

When I touched the code, I started wondering if we should restrict the mul! methods to the cases where the plan and the array dimension match and then only support the implicit broadcasting cases for fft and rfft and do so via mapslices to keep things simple.

[wheeheee]

Might break the AbstractFFTs interface, and I don't think complete type stability is worth that. As it is, the impact is barely noticeable for non-trivial procedures. And IIRC mapslices is also not type-stable internally.

[dannys4]

Might break the AbstractFFTs interface, and I don't think complete type stability is worth that.

You have more faith in the interface than I.

mapslices is also not type-stable internally.

But it could be type-stable one day.

let me know when you resolve the conflicts and I'll review/approve.

[wheeheee]

let me know when you resolve the conflicts and I'll review/approve.

Done. The CI failure is from that N=73^2 test on 1.6...

[dannys4]

This largely looks good but is there any test of correctness? I obviously see the tests for the errors, but it would be nice to have a reference test for something we know the FFT of. For example, if $[A]_{ijk}$ is one at $i=j=k=1$ and zero elsewhere or is one everywhere. This obviously is absolutely not going to go through the paces that we probably should, but I think relying on the more general tests for one-dimensional cases is fine. Codecov is likely missing it because of generated function stuff.

[wheeheee]

I did manually test against FFTW for a random complex 3D array, and it was fine. But doing that in runtests.jl might hit #66 so idk. But the lazy way is to just test the FFTs of a few 3x3x3 arrays with one entry set to 1. Or just paste a few random arrays and the FFTW output from them.
edit: ok, there is naive_1d_fourier_transform and naive_2d_fourier_transform, so...naive_3d_fourier_transform?

[dannys4]

yeah I'm not too picky on regression or whatever---I just want to make sure that it actually runs without error on a few different sizes (e.g., (3,5,7), (2*13,3*11,5*7, 4), etc.) Really, ones that have different plans in different dimensions.

[wheeheee]

There is a new (and even weirder) error on 1.6...

[dannys4]

overall looks great. Sorry to be a pain about backward compatibility. Fwiw, the 1.6 locally doesn't fail the 73^2 test 😬

[wheeheee]

Base.size for FFTAPlan_re looks inconsistent so I just fixed that, the rest is mostly formatting. Although it does look like a lot of lines changed so lmk if you want this in a separate PR.

[dannys4]

looks great, thanks for the pr!

[wheeheee]

overall looks great. Sorry to be a pain about backward compatibility. Fwiw, the 1.6 locally doesn't fail the 73^2 test 😬

Hm, if your local 1.6 isn't 1.6.0 (min), it's possible that the bug was fixed in a patch release. We could experiment...