acb_dft.h

This module computes the discrete Fourier transform (DFT) of a vector of complex balls,

for any length $n \ge 1$, and its inverse $v_j = \frac{1}{n} \sum_{k} w_k e^{2\pi i jk/n}$. The output balls contain the exact transform of every complex vector in the input balls.

All functions are thin wrappers around the complex ball transforms of gr_dft: acb_dft calls gr_dft_acb, and acb_dft_pre_t is the plan type gr_dft_acb_pre_t. These run the transform on the midpoints in fixed-point arithmetic with an a priori error bound, and fall back to ball arithmetic when fixed point does not apply (non-finite or extremely large midpoints); see Transforms of complex ball vectors for the method and Rigorous numerical DFTs in fixed point for the error analysis. The plan chooses among radix-2, split-radix, four-step, Good–Thomas, mixed-radix and Bluestein algorithms according to the factorisation of $n$ (Discrete Fourier transforms over a generic ring), so that a transform costs $O(n \log n)$ operations for every $n$.

Earlier versions of this module also provided product DFTs, cyclic convolutions and direct access to the naive, CRT, cyclic, radix-2 and Bluestein algorithms. These have been removed: product DFTs of complex ball vectors are gr_dft_acb_prod, transforms on groups of Dirichlet characters are acb_dirichlet_dft, and the individual algorithms, transforms over other rings and convolutions are in gr_dft.