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.

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