Module transform 

The discrete Fourier transform, as a kernel utility.

Numerics rather than physics, which is why it belongs here alongside integrator and vector rather than in any domain. It arrived in dualis-optics because that is where it was first needed — twice, for pupil transforms and for angular-spectrum propagation — and it stayed there one domain too long. An electrostatic solver needs the same transform for Ewald summation, and a domain crate cannot reach into another one.

Accuracy over speed, deliberately

The twiddle factors are computed from cos and sin at every butterfly rather than accumulated by repeated complex multiplication. Accumulating is faster and loses several digits by the end of a long transform. This is a physics library: a result wrong in its fourth digit is not worth the cycles saved, and the transforms here are small.

It also keeps the answer independent of how the loops were ordered, which is the same reason every other reduction in this workspace is written in a fixed sequence.

Radix two only

Lengths must be powers of two, and that is enforced rather than worked around. A mixed-radix implementation would be several times the code for a case nothing here has needed, and silently padding a caller’s array would change the frequency grid underneath them.

Sign convention

The forward transform carries exp(-2πi jk/N) and the inverse carries exp(+2πi jk/N) with a 1/N in front, so that ifft(fft(x)) == x. That is the convention physics and signal processing agree on; some numerical libraries put the 1/N on the forward transform instead, and a field propagated with one and read back with the other comes out scaled by N².

Functions

fft

In-place one-dimensional transform on split real and imaginary parts.

fft2

In-place two-dimensional transform of an n-by-n array in row-major order.

fftshift

Swap quadrants so the zero frequency sits at the centre of the array.

ifft

In-place one-dimensional inverse transform, including the 1/N.

ifft2

In-place two-dimensional inverse transform, including the 1/N².