FLINT3.7.0-dev
/
Overview

Multivariate polynomials

The sections below describe the algorithms behind the sparse multivariate polynomial modules fmpz_mpoly, fmpq_mpoly, nmod_mpoly, fmpz_mod_mpoly, fq_nmod_mpoly, fq_zech_mpoly and gr_mpoly, their factorisation modules and the rational function modules. The overview compares the methods and says which functions use them; the others give the algorithms with proofs, starting from the representation of polynomials, through arithmetic, to GCDs and factorisation. Those on GCDs over small finite fields, factoring over finite fields and bivariate resultants treat what is specific to finite fields.

In this section#

OverviewMultivariate polynomials: representations and algorithmsAn overview of FLINT's sparse multivariate polynomial modules: which coefficient rings they cover, how polynomials are represented, and which algorithms are used for multiplication, division, powering, square roots, GCDs, resultants and factorisation, with links to the detailed pages.AlgorithmMonomial orderings and exponent packingHow FLINT stores sparse multivariate polynomials: terms sorted by a monomial ordering, exponent vectors packed into machine words so that comparing, multiplying and dividing monomials are word operations, with guard bits for overflow detection; and the deflations, repackings and changes of variables that the algorithms apply to this representation.AlgorithmSparse and dense multiplicationMultiplication of sparse multivariate polynomials with Johnson's heap algorithm and the improvements of Monagan and Pearce (packed monomials, chaining, small heaps, three-word accumulation, parallel splitting of the output), dense array accumulation, Kronecker substitution for dense inputs, and powering by the FPS recurrence.AlgorithmDivision, exact division and square rootsMultivariate division with remainder with respect to a monomial ordering, and its heap implementation by Monagan and Pearce, in which a heap of size at most the number of terms of the divisor supplies the terms of the current remainder; early termination of exact division, quasi-division over the integers, division by several polynomials, parallel exact division, and the analogous heap algorithm for square roots with its non-square certificates.AlgorithmGreatest common divisorsHow FLINT computes GCDs of multivariate polynomials over the integers: reductions that make most inputs easy (monomial content, deflation, missing variables, univariate cases), degree bounds from random images, and the four modular algorithms it chooses between (Brown's dense algorithm, Zippel's sparse algorithm, the Berlekamp–Massey based algorithm of Hu and Monagan, and EEZ-GCD Hensel lifting), with their correctness proofs and the cost model behind the choice.AlgorithmGCDs over small finite fieldsHow the multivariate GCD algorithms over \mathbb{F}_p and \mathbb{F}_q cope with fields too small for random evaluation points, by computing images over extension fields \mathbb{F}_{p^k} or modulo irreducible polynomials of increasing degree; Brown's algorithm over \mathbb{F}_p with pairs of points and early termination; and how nmod_mpoly_gcd chooses among Brown's, Zippel's and Hensel-lifting algorithms.AlgorithmSparse interpolationRecovering a sparse polynomial from its values at a few points: Zippel's method for a known support (transposed Vandermonde systems solved in quadratic time, with extra unknowns for scaled images), and the method of Ben-Or and Tiwari for an unknown support (Berlekamp–Massey, roots of the recurrence polynomial, discrete logarithms modulo a smooth prime after Kronecker substitution) with the Berlekamp–Massey algorithm computed incrementally by half-gcd steps, as used by FLINT's sparse GCD and factoring algorithms.AlgorithmMultivariate Hensel liftingLifting a factorisation of A(x_0, \alpha_1, \ldots, \alpha_m) to a factorisation of A one variable at a time: uniqueness given the leading coefficients, the multivariate partial fraction (diophantine) equations solved by Taylor expansion, the quartic and quintic error updates of FLINT's fmpz_mpoly_hlift, bivariate lifting modulo prime powers, sparse lifting, and the leading coefficient methods of Wang and Kaltofen.AlgorithmFactorisationHow FLINT factors multivariate polynomials over the integers: removal of contents and powers of variables, squarefree decomposition by Yun's algorithm, compression of the exponents by unimodular changes of variables, irreducibility certificates from Newton polytopes, direct formulas for low degree, dense bivariate factorisation with Hensel lifting and recombination, degree pruning with univariate images, and the three lifting strategies of Wang, Zippel and Zassenhaus.AlgorithmFactoring over finite fieldsThe multivariate factorisation pipeline of nmod_mpoly_factor and fq_nmod_mpoly_factor, with what is specific to characteristic p: separable factorisation with p-th roots, deflation by powers of p, factoring over extension fields with recombination of Frobenius orbits when the field is too small for good evaluation points, quadratic equations in characteristic 2, bivariate factorisation with recombination by linear algebra, and Wang's leading coefficients along random curves.AlgorithmBivariate resultants by evaluation and interpolationThe resultant \mathrm{Res}_y(A, B) \in \mathbb{F}_p[x] of two bivariate polynomials, computed from univariate resultants at many values of x (a geometric progression or roots of unity) and interpolation, with the degree bound, the correction for specialisations that lower the degree, and FLINT's cutoffs.
Cite this page

The FLINT team, “Multivariate polynomials,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/multivariate/index.html (generated 2026-10-20).