FFTs in FLINT

A fast Fourier transform evaluates a polynomial of length L at the L powers of a root of unity of order L in O(L \log L) ring operations, and the inverse transform interpolates. Multiplying two polynomials then costs two transforms, L pointwise products and one inverse transform, and integers are multiplied the same way after cutting them into coefficients. The ring in which the transform runs decides almost everything else: how the roots of unity are represented, how large the coefficients of the product may be, and how fast a butterfly is on current hardware. FLINT has one implementation for each of three choices.

The three implementations#

The first two exist to multiply. The Schönhage–Strassen transform needs no multiplications at all, only shifts and additions of multi-limb numbers, and its ring grows with the operands, which gives the bound O(n \log n \log \log n) for n-bit products [SS1971]. The small-prime transform does the opposite: it keeps every number in the 53-bit significand of a double, so that a butterfly is a handful of vector instructions, and it recovers large coefficients by transforming modulo several primes and combining the results with the Chinese remainder theorem. On processors with wide FMA units the second approach wins at every size FLINT is tuned for: the overview of the fft module measures fft_small at 1.5 to 2 times the speed of flint_mpn_mul_fft_main where both apply. The third implementation is not a multiplication engine but a general DFT library, for transforms of any length over any ring and for numerical transforms with proven error bounds.

Which one a product uses#

Users rarely call a transform directly; the multiplication functions choose by size.

• Integers. flint_mpn_mul uses FLINT's own small-size code and Karatsuba, then GMP's mpn_mul, and for large operands mpn_mul_default_mpn_ctx of fft_small, from a smaller operand of FLINT_FFT_SMALL_MUL_THRESHOLD limbs (500 on recent Intel processors; Callers and thresholds lists the other targets). Builds without fft_small call flint_mpn_mul_fft_main of fft instead, from FLINT_FFT_MUL_THRESHOLD = 32000 limbs. Everything built on flint_mpn_mul, starting with fmpz_mul, inherits this choice.
• Polynomials over \mathbb{Z}/n\mathbb{Z}. nmod_poly_mul and its low, middle and high variants use classical multiplication, then Kronecker substitution, then fft_small, with cutoffs that depend on the bit size of n (Multiplying polynomials over Z/nZ). Kronecker substitution ends in an integer product, so its large cases also reach an FFT, through flint_mpn_mul.
• Polynomials over \mathbb{Z}. For most large inputs fmpz_poly_mul calls _fmpz_poly_mul_mid_default_mpn_ctx, a direct multimodular product with up to eight 50-bit primes of fft_small, when the coefficients of the product (plus the growth from the length) have up to about 397 bits, and Kronecker substitution, whose integer product also uses fft_small, beyond that. It uses Schönhage–Strassen convolutions (fft_convolution) for huge products, for some squarings and middle products, and with four or more threads (Multiplying polynomials over Z). The pointwise products of those convolutions are computed by fft_small again (Multiplication modulo 2^N + 1).
• Matrices. fmpz_mat_mul_fft_small and nmod_poly_mat_mulmid_fft_small transform each entry once and do the matrix products in transform space, so that O(n^2) transforms serve n^3 pointwise products (Sums of products and fixed operands).
• Complex numbers. acb_dft and acb_dirichlet_dft are wrappers around gr_dft, which computes rigorous enclosures in fixed-point arithmetic when it can (Transforms of complex ball vectors).

Shared techniques#

The implementations differ in their rings but share most of their structure.

Truncation. A radix-2 transform for a product of length t needs length L = 2^{\lceil \log_2 t \rceil}, which wastes up to half of the work just above a power of two. Van der Hoeven's truncated FFT computes only the t values needed and inverts from them in about (t/2) \log_2 L butterflies. Both multiplication engines use it.

AlgorithmTruncated FFTsVan der Hoeven's truncated Fourier transform evaluates a polynomial of length t at the first t points of an FFT of length L = 2^\ell \ge t in about (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.

Cache blocking. A long transform is split as L = L_1 L_2 into short transforms that fit in cache: Bailey's four-step or matrix Fourier algorithm. fft uses it from a tuned size on, fused with the pointwise products; fft_small applies the same decomposition recursively, in a form without twiddle multiplications (Blocking); gr_dft offers it as one of its plan types.

AlgorithmThe matrix Fourier algorithmBailey's four-step algorithm computes an FFT of length n_1 n_2 as n_1 transforms of length n_2, twiddle factors and n_2 transforms of length n_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.

Several primes and the CRT. When the coefficients of a product do not fit modulo one prime, the product is computed modulo several and reconstructed. Matrix multiplication over \mathbb{Z}/n\mathbb{Z} uses the same idea with floating-point matrix products (Matrix multiplication kernels modulo n).

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.

Middle products and wrap-around. A cyclic convolution of length L gives the product modulo x^L - 1. When only a window of the product is needed, the wrapped-around terms may be allowed to land outside the window, which can save up to half of the transform length when a power of two lies in the right place. The transposition principle gives the saving for every length: fft_small has transposed versions of its truncated transforms, with which a middle product costs a product of the output length and the shorter operand. nmod_poly_mulmid, flint_mpn_mulmid and radix_mulmid use them for windows shorter than the longer operand when the transform is shorter (_nmod_poly_mul_tr_mpn_ctx, _mpn_ctx_mpn_mul_range, radix_mulmid_fft_small), and the evaluation and extrapolation at geometric progressions keep the transposed transform of their fixed polynomial (_mul_precomp_init_tr).

AlgorithmMiddle products and the transposition principleThe middle product, a window of coefficients of a product, is the transpose of polynomial multiplication and costs no more than an ordinary product of the corresponding size; FLINT computes it with dot products, a cyclic convolution whose wrap-around misses the window, or transposed FFTs, and uses it in Newton iteration and geometric evaluation.

Kronecker substitution turns polynomial products into integer products, which is how the integer FFTs serve polynomial arithmetic.

AlgorithmKronecker substitutionMultiplies polynomials over \mathbb{Z}/n\mathbb{Z} by packing their coefficients into large integers, multiplying the integers and unpacking; Harvey's KS2 and KS4 variants evaluate at ±2^b and ±2^(-b) to split the integer product into two or four smaller ones.

Using the transforms directly#

Each module has a guide for those who need the transforms rather than a finished product: Multiplying integers and polynomials multiplies integers by hand with the splitting, convolution and recombination functions of fft; Arithmetic in transform space keeps operands transformed and accumulates products in transform space with fft_small; and Getting started computes DFTs over \mathbb{Z}/p\mathbb{Z} and the complex numbers with gr_dft.

@misc{flint-doc-algorithms-fft-choosing,
  author       = {{The FLINT team}},
  title        = {{FFTs in FLINT}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/fft/choosing.html},
  note         = {Generated 2026-10-20}
}