Search papers, labs, and topics across Lattice.
This paper addresses the singularity issue in the Linzer-Feig radix-2 FFT butterfly factorization, which arises from precomputing $\cot\theta$ and leads to numerical instability when $\sin\theta$ approaches zero. They propose a dual-select strategy that dynamically chooses between factorizations using either $\cot\theta$ or $\tan\theta$ based on which yields a ratio with an absolute value less than or equal to 1. By eliminating the need for epsilon clamping, the dual-select method significantly improves numerical precision, achieving a 235x tighter error bound in FP16 arithmetic for N=1024 over 10 FFT passes, without adding computational overhead.
A simple tweak to FFT twiddle factor precomputation eliminates singularities and dramatically improves numerical precision, offering a free upgrade for anyone using FFTs.
The fused multiply-add (FMA) instruction enables the radix-2 FFT butterfly to be computed in 6~FMA operations -- the proven minimum. The classical factorization by Linzer and Feig~\cite{linzer1993} precomputes the ratio $\cot\theta = \cos\theta/\sin\theta$, which is singular when the twiddle factor is $W^0 = 1$ (i.e., $\sin\theta = 0$). Standard practice clamps $\sin\theta$ to a small epsilon, degrading numerical precision. We observe that an alternative factorization using $\cos\theta$ as the outer multiplier (precomputing $\tan\theta$) avoids this particular singularity but introduces a new one at $W^{N/4}$. We then propose a \emph{dual-select} strategy that chooses, per twiddle factor, whichever factorization yields $|\text{ratio}| \leq 1$. This eliminates all singularities, requires no epsilon clamping, and bounds the precomputed ratio to unity for all twiddle factors. For $N = 1024$, the worst-case ratio drops from 163 (Linzer-Feig) to exactly~1.0 (dual-select), yielding a $235\times$ tighter error bound in FP16 arithmetic over 10~FFT passes. The strategy adds zero computational overhead -- only the precomputed twiddle table changes.
