FLINT3.7.0-dev
/
Overview

Fast Fourier transforms

FLINT has three FFT implementations, each suited to different coefficient rings and sizes. The sections below describe the transforms, their truncated and cache-friendly variants, and how they are combined with the Chinese remainder theorem to multiply large integers and polynomials.

In this section#

OverviewFFTs in FLINTFLINT has three FFT implementations — Schönhage–Strassen over Z/(2N+1)Z\mathbb{Z}/(2^N+1)\mathbb{Z}, small-prime transforms in floating point, and generic DFTs over any ring. This page compares them, says which one each multiplication routine uses, and maps the techniques they share.AlgorithmSchönhage–Strassen multiplicationMultiplies large integers with FFTs over Z/(2N+1)Z\mathbb{Z}/(2^N + 1)\mathbb{Z}, where the roots of unity are powers of 2 and every twiddle factor is a shift; FLINT adds the 2\sqrt 2 trick, truncation, negacyclic pointwise products and tuned parameters.AlgorithmTruncated FFTsVan der Hoeven's truncated Fourier transform evaluates a polynomial of length tt at the first tt points of an FFT of length L=2ℓ≥tL = 2^\ell \ge t in about (t/2)log⁡2L(t/2) \log_2 L butterflies, and its inverse recovers the polynomial from these values, which removes the jumps of radix-2 convolution at powers of two.AlgorithmThe matrix Fourier algorithmBailey's four-step algorithm computes an FFT of length n1n2n_1 n_2 as n1n_1 transforms of length n2n_2, twiddle factors and n2n_2 transforms of length n1n_1, so that each partial transform fits in cache; FLINT fuses it with the pointwise products of a convolution, truncates at whole rows and runs the partial transforms in threads.AlgorithmFFTs modulo word-size primes in floating pointThe number-theoretic transforms of fft_small modulo primes p<250p < 2^{50}, on integers stored in doubles: the order of the roots, radix-4 butterflies with lazy reduction, blocking and truncation, and proofs that every value stays in range.AlgorithmMultiplication with several primes and CRTHow fft_small multiplies integers and polynomials whose product coefficients exceed one prime: chunk sizes and the number of primes, the two-prime and multi-prime pipelines, Chinese remaindering with the normalisation folded in, windows computed with wrap-around, sums of products in transform space, precomputed and shared operands, and transposed products for middle products.AlgorithmDiscrete Fourier transforms over a generic ringThe DFT algorithms of gr_dft (naive, radix-2 and split-radix Cooley–Tukey, four-step, mixed-radix with direct prime kernels, Good–Thomas and Bluestein), the conditions each one needs on the root of unity, and their costs.AlgorithmRigorous numerical DFTs in fixed pointHow gr_dft computes complex DFTs in multi-limb fixed-point arithmetic with an a priori bound on every intermediate value and on the output error, and how this yields ball enclosures for transforms of acb vectors.
Cite this page

The FLINT team, “Fast Fourier transforms,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/fft/index.html (generated 2026-11-02).