UDFT: Unitary Discrete Fourier Transform (and related)

This module implements unitary (orthonormal) discrete Fourier transforms and related functions for convolution. It is built on top of the Array API standard via array-api-compat, making it compatible with NumPy, PyTorch, and other compliant array libraries.

It is useful for convolution [1]: they respect the Parseval equality \(\|x\|_2^2 = \|X\|_2^2\), e.g., the value of the null frequency \(X_0\) is equal to

\[X_0 = \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x_n, \text{ and } x_0 = \frac{1}{\sqrt{N}} \sum_{n'=0}^{N-1} X_{n'}.\]

and if \(H\) is a circulant convolution with \(h\) as a real impulse response, then \(H = F^* \Lambda F\) where \(F^*\) is the unitary IDFT computed by irdftn(), \(F\) the unitary DFT computed by rdftn(), and \(\Lambda\) the frequency response computed with ir2fr() from \(h\).

[1] B. R. Hunt "A matrix theory proof of the discrete convolution theorem",
IEEE Trans. on Audio and Electroacoustics, vol. au-19, no. 4, pp. 285-288,
dec. 1971

If you are having issues, please let me know:

francois.orieux AT universite-paris-saclay.fr

Installation

UDFT is a single file (udft.py) requiring Python >= 3.12. Install with pip:

pip install udft

For multithreaded FFT on NumPy arrays, install the optional SciPy dependency:

pip install udft[scipy]

The project follows Semantic Versioning.

Using udft with AI agents

• llms.txt follows the llms.txt proposal and gives agents a map of this documentation.

• skills/udft is an Agent Skill that teaches agents the conventions of udft (unitary normalization, last axes, irdftn shape, ir2fr convolution model). In Claude Code, install it from the repository, which is also a plugin marketplace:

  /plugin install udft --marketplace forieux/udft
  

  or, in two steps, /plugin marketplace add forieux/udft then /plugin install udft@udft. For other agents, copy the skills/udft directory into their skills directory.

How AI is used

This project is not vibecoded. But with performant AI agents, I use them for bug tracking and design reflection, not for code writing. I write the code, but the one proposed by the agent is in the window on the side, obviously.

The agent and I write documentation. I reread the agent part, and the agent reread my part, and I chose to commit. The agent writes all tests. I chose that approach because I don’t have the time to write all the documentation and tests.

I think this is a good trade-off for a project maintained by one person. It allows me to propose a more polished version of what I publish, as if I were a full-time developer, which is also good for my own use.

License

The code is in the public domain.

Contents

• Discrete Fourier Transform
  • dftn
  • idftn
  • dft
  • idft
  • dft2
  • idft2
• Real Discrete Fourier Transform
  • rdftn
  • irdftn
  • rdft
  • rdft2
• Convolution related
  • ir2fr
  • fr2ir
  • diff_ir
  • laplacian
• Other
  • hnorm
  • crandn