Fourier Toolkit

Fourier Toolkit (FTK) is a collection of utilities to compute Fourier sums.

Rationale

Fourier operators are pervasive in science and engineering as waves are the main vector of information transfer in physical systems. Casting wave problems in discrete form leads to the evaluation of sums of the form

(1)\[\bbz_{n} = \sum_{m=0}^{M-1} w_{m} \ee^{-\cj 2 \pi \innerProduct{\bbx_{m}}{\bbv_{n}}}, \qquad n \in \{0,\ldots,N-1\},\]

where \(\{\bbx_{m} \in \bR^{D}\}\) and \(\{\bbv_{n} \in \bR^{D}\}\) are known constants refered to as knots. This equation computes Fourier Transform samples of the Dirac stream \(f(\bbx) = \sum_{m} w_{m} \delta(\bbx - \bbx_{m})\) at frequencies \(\bbv_{n}\).

Naive evaluation of (1) costs \(\cO(M N)\) operations which is intractable at scale. There is a rich literature on low-complexity methods to compute the latter more efficiently depending on the distribution of spatial/spectral knots [1, 2, 3, 4, 5, 6, 7, 8, 9]. At their core, they all leverage the Fast Fourier Transform algorithm (FFT) in some form to perform the bulk of the work:

• When the \((\bbx_{m}, \bbv_{n})\) knots lie on uniform grids, we talk of uniform-to-uniform methods: one or two FFTs suffice to evaluate (1).

• When either \((\bbx_{m}, \bbv_{n})\) are non-uniform, we talk of Non-uniform FFTs: the latter combine the FFT with convolution/interpolation steps to compute (1) within a chosen relative error \(\epsilon \ll 1\).

FTK is thus a toolbox to evaluate Fourier sums efficiently by building on mature libraries.

Setup

# user install
pip install fourier_toolkit@git+https://github.com/SepandKashani/fourier_toolkit.git

# developer install
git clone https://github.com/SepandKashani/fourier_toolkit.git
cd fourier_toolkit/
uv sync --group dev
uv run pre-commit install

# run test suite
uv run pytest

# build HTML docs
uv run make -C doc/ html

# creating a release
uv run dev/create_release.py <version>