FLINT3.7.0-dev
Algorithm

Bivariate resultants by evaluation and interpolation

Cost
O((nA+nB)M(N)+NM(nA)log⁡nA)O((n_A + n_B) M(N) + N M(n_A) \log n_A) operations in Fp\mathbb{F}_p for N=nBdA+nAdB+1N = n_B d_A + n_A d_B + 1 points, where nA,nBn_A, n_B are the degrees in the eliminated variable and dA,dBd_A, d_B those in the other one.

Let A,B∈Fp[x][y]A, B \in \mathbb{F}_p[x][y] have degrees nA=deg⁡yA≥1n_A = \deg_y A \ge 1 and nB=deg⁡yB≥1n_B = \deg_y B \ge 1 in yy and degrees dAd_A, dBd_B in xx. Their resultant with respect to yy is the determinant of the Sylvester matrix, a polynomial R=Resy(A,B)∈Fp[x]R = \mathrm{Res}_y(A, B) \in \mathbb{F}_p[x]. The subresultant algorithm computes it by pseudo-remainder sequences in Fp[x][y]\mathbb{F}_p[x][y], whose intermediate coefficients have growing degree in xx. When Fp\mathbb{F}_p is large enough, it is faster to evaluate xx at many points, compute univariate resultants over Fp\mathbb{F}_p, and interpolate, as in the classical modular resultant algorithm [GG2003, §6.9]. FLINT implements this method for nmod_mpoly with fast evaluation and interpolation at structured points: a geometric progression [BS2005], or roots of unity when pp is an FFT prime.

Degree bound and specialisation#

Lemma 1 (Degree bound). deg⁡xR≤nBdA+nAdB\deg_x R \le n_B d_A + n_A d_B.

Proof. The Sylvester matrix has nBn_B rows of coefficients of AA (polynomials in xx of degree at most dAd_A) and nAn_A rows of coefficients of BB (degree at most dBd_B). Every term of the expansion of the determinant is a product of one entry from each row.

Hence RR is determined by its values at N=nBdA+nAdB+1N = n_B d_A + n_A d_B + 1 distinct points, the number Collins [Col1971] takes for each variable in turn. The value at x=ax = a must be computed from the specialisations f=A(a,y)f = A(a, y) and g=B(a,y)g = B(a, y), whose degrees may be lower than nAn_A and nBn_B when aa is a root of a leading coefficient.

Lemma 2 (Specialisation). Let a∈Fpa \in \mathbb{F}_p, f=A(a,y)f = A(a, y), g=B(a,y)g = B(a, y), and ℓA\ell_A, ℓB\ell_B the leading coefficients of AA and BB in yy.

  1. If deg⁡f=nA\deg f = n_A, then R(a)=ℓA(a)nB−deg⁡gRes(f,g)R(a) = \ell_A(a)^{n_B - \deg g} \mathrm{Res}(f, g).
  2. If deg⁡g=nB\deg g = n_B and deg⁡f<nA\deg f < n_A, then R(a)=(−1)nB(nA−deg⁡f)ℓB(a)nA−deg⁡fRes(f,g)R(a) = (-1)^{n_B (n_A - \deg f)} \ell_B(a)^{n_A - \deg f} \mathrm{Res}(f, g).
  3. If both degrees drop, R(a)=0R(a) = 0.

Here Res(f,g)\mathrm{Res}(f, g) is the resultant of ff and gg with respect to their actual degrees, and is 0 if ff or gg is zero.

Proof. Evaluation commutes with the determinant, so R(a)R(a) is the determinant of the Sylvester matrix of ff and gg built with the formal degrees nAn_A and nBn_B. In case 1, the leading nB−deg⁡gn_B - \deg g coefficients of gg in that matrix are zero, and expanding along the first columns, each of which then has the single nonzero entry ℓA(a)\ell_A(a), gives the formula. Case 2 follows from case 1 applied to Resy(B,A)=(−1)nAnBR\mathrm{Res}_y(B, A) = (-1)^{n_A n_B} R, with the sign of the exchange for the actual degrees. In case 3, the first column of the matrix contains only ℓA(a)=ℓB(a)=0\ell_A(a) = \ell_B(a) = 0.

Algorithm#

Algorithm 1: Bivariate resultant by multipoint evaluation

Input: A,BA, B with nA≥nB≥1n_A \ge n_B \ge 1 and a prime pp. Output: R=Resy(A,B)R = \mathrm{Res}_y(A, B), or failure if Fp\mathbb{F}_p is too small.

  1. Set N=nBdA+nAdB+1N = n_B d_A + n_A d_B + 1.
  2. Choose NN distinct points: if FLINT has fft_small and p−1p - 1 is divisible by 2k≥max⁡(N,16)2^k \ge \max(N, 16) (an FFT prime), the powers of a primitive 2k2^k-th root of unity ww; otherwise a geometric progression 1,q,q2,…,qN−11, q, q^2, \ldots, q^{N-1} with q=r2q = r^2 of order at least NN, where rr is the first of 2,3,4,…2, 3, 4, \ldots that works. If p<2N+1p < 2N + 1, no such qq exists: fail.
  3. Evaluate each of the nA+nB+2n_A + n_B + 2 coefficients of AA and BB (as polynomials in xx) at the points, by FFTs or by the geometric progression algorithm [BS2005], in blocks of points sized to bound the memory.
  4. At each point, compute the univariate resultant of the specialisations with _nmod_poly_resultant and apply Lemma 2.
  5. Interpolate RR from its NN values, by an inverse FFT or geometric interpolation.

The evaluation of one coefficient of length at most max⁡(dA,dB)+1\max(d_A, d_B) + 1 at NN points of a geometric progression costs O(M(N))O(M(N)) operations, so step 3 costs O((nA+nB)M(N))O((n_A + n_B) M(N)), step 5 costs O(M(N))O(M(N)), and step 4 costs NN univariate resultants of degree nAn_A, each O(M(nA)log⁡nA)O(M(n_A) \log n_A) with the half-gcd algorithm (Half-GCD) or O(nAnB)O(n_A n_B) with Euclid's algorithm for small degrees. In the FFT case the points are split into 2depth−m2^{\mathrm{depth} - m} cosets of the 2m2^m-th roots of unity, each evaluated by a substitution x↦wtxx \mapsto w^t x and one transform of length 2m2^m; the values come out in the order that the truncated inverse transform needs, so interpolation is a single inverse transform (or a geometric interpolation with r=wr = \sqrt{w} when that is cheaper). Both loops over the points run in parallel on the threads set with flint_set_num_threads when the work is large enough.

More variables: Kronecker substitution#

Let now A,B∈Fp[x1,…,xk][y]A, B \in \mathbb{F}_p[x_1, \ldots, x_k][y], of degrees nAn_A, nB≥1n_B \ge 1 in yy and dA,jd_{A,j}, dB,jd_{B,j} in xjx_j. A ring homomorphism ϕ\phi of the coefficient ring that keeps the leading coefficients in yy nonzero commutes with the resultant, since the resultant is a polynomial in the coefficients: ϕ(Resy(A,B))=Resy(ϕ(A),ϕ(B))\phi(\mathrm{Res}_y(A, B)) = \mathrm{Res}_y(\phi(A), \phi(B)). Three such maps reduce the problem to Algorithm 1.

  1. Monomial factors. If A=xaA′A = x^a A', then Resy(A,B)=xanBResy(A′,B)\mathrm{Res}_y(A, B) = x^{a n_B} \mathrm{Res}_y(A', B), and similarly for BB; both are shifted down to their minimal exponent in each xjx_j.
  2. Deflation. If every exponent of xjx_j left in AA and BB is a multiple of gjg_j, the map xj↦xjgjx_j \mapsto x_j^{g_j} is injective and its inverse is applied to both.
  3. Kronecker substitution [Kro1882]. With DjD_j one more than a bound on the degree in xjx_j of the resultant of the shifted and deflated polynomials, the map xj↦tSjx_j \mapsto t^{S_j} with Sj=D1⋯Dj−1S_j = D_1 \cdots D_{j-1} is injective on the polynomials of degree less than DjD_j in each xjx_j.

The resultant is then recovered from its image in Fp[t]\mathbb{F}_p[t] by reading off the digits of each exponent of tt in the mixed radix (D1,…,Dk)(D_1, \ldots, D_k), and Algorithm 1 needs D1⋯DkD_1 \cdots D_k points: exactly one per coefficient of the dense box of the resultant. The packed coefficients of AA and BB hold at most as many entries, so the memory used is of the order of the size of that box. The bounds come from the following refinement of Lemma 1.

Lemma 3 (Weighted degree bound). Let w≥0w \ge 0, and let a(w)a(w) be the largest value of e+wme + w m over the terms xjeymx_j^e y^m of AA (the other variables being ignored), and b(w)b(w) that over the terms of BB. Then

deg⁡xjResy(A,B)≤nB a(w)+nA b(w)−w nAnB.\deg_{x_j} \mathrm{Res}_y(A, B) \le n_B\, a(w) + n_A\, b(w) - w\, n_A n_B.

Proof. Row i<nBi < n_B of the Sylvester matrix holds the coefficient of yc−iy^{c-i} in AA in column cc, a polynomial of degree at most a(w)+wi−wca(w) + w i - w c in xjx_j, and row nB+in_B + i holds that of BB, of degree at most b(w)+wi−wcb(w) + w i - w c. A term of the determinant takes one entry in each row and each column, so its degree is at most the sum of these over the rows less ww times the sum of the column indices, which is the right-hand side.

The weight w=0w = 0 gives nBdA,j+nAdB,jn_B d_{A,j} + n_A d_{B,j} as in Lemma 1, which is reached by polynomials dense in a box. The weight w=1w = 1 gives the Bézout bound dAdBd_A d_B when AA and BB have total degrees dAd_A and dBd_B in (xj,y)(x_j, y) and the same degrees in yy: half as much, and the box of the resultant of two such polynomials in three variables has four times fewer coefficients. The right-hand side is a convex, piecewise linear function of ww, and a(w)a(w) only depends on the upper convex hull of the points (m,e)(m, e), so its minimum is at w=0w = 0 or at a slope ww of that hull for AA or for BB; FLINT takes the minimum over these. Since b(w)≥wnBb(w) \ge w n_B, the bound is at least nBdA,jn_B d_{A,j} and nAdB,jn_A d_{B,j}, so the substitution is also injective on AA and BB, and keeps their leading coefficients in yy nonzero.

The images of AA and BB have degree at most ∑jdA,jSj\sum_j d_{A,j} S_j and ∑jdB,jSj\sum_j d_{B,j} S_j in tt, so that the bound of Lemma 1 on the degree of their resultant is

∑j(nBdA,j+nAdB,j)Sj+1≥∑j(Dj−1)Sj+1=D1⋯Dk,\sum_j (n_B d_{A,j} + n_A d_{B,j}) S_j + 1 \ge \sum_j (D_j - 1) S_j + 1 = D_1 \cdots D_k,

with equality when every DjD_j comes from the weight 0, and Algorithm 1 is told the number of points D1⋯DkD_1 \cdots D_k. Applied to the substitution xj↦sxjx_j \mapsto s x_j for all jj at once, Lemma 3 also bounds the total degree of the resultant in the xjx_j, which tells how much of the box the resultant can fill: about half of it for inputs dense in total degree with two variables packed, a sixth with three.

Over Z\mathbb{Z} the substitution changes neither the coefficients nor their norms, so the multimodular algorithm and its coefficient bound apply to the images unchanged.

Collins [Col1971] eliminates the variables one at a time instead: each xjx_j in turn is evaluated at nBdA,j+nAdB,j+1n_B d_{A,j} + n_A d_{B,j} + 1 points, down to univariate resultants, which are interpolated back one variable at a time. Both take one univariate resultant per point of the box. The substitution turns the nested evaluations and interpolations into a single one in tt, which Algorithm 1 does with fast algorithms on structured points. Hu and Monagan [HuMon2016] pack the variables of a sparse GCD problem the same way, leaving the main variable alone. For GCDs some substitutions are unlucky and have to be detected. There are none for the resultant: it commutes with every substitution that keeps the leading coefficients in yy nonzero, so being injective on the resultant is enough.

Example#

Two random polynomials of degree 8 in each variable modulo the prime 106+310^6 + 3; nmod_mpoly_resultant takes the evaluation and interpolation path, and the result agrees with the subresultant algorithm applied to the univariate forms. The resultant reaches the degree bound of Lemma 1:

Examplenmod_mpoly_bivariate_resultant.cchecked by make checkdoc
#include <flint/flint.h>
#include <flint/nmod_mpoly.h>

int main(void)
{
    nmod_mpoly_ctx_t ctx;
    nmod_mpoly_t a, b, r1, r2;
    nmod_mpoly_univar_t ua, ub;
    ulong bounds[2] = {9, 9};     /* degrees < 9 in x and in y */
    flint_rand_t state;

    flint_rand_init(state);
    nmod_mpoly_ctx_init(ctx, 2, ORD_LEX, UWORD(1000003));
    nmod_mpoly_init(a, ctx); nmod_mpoly_init(b, ctx);
    nmod_mpoly_init(r1, ctx); nmod_mpoly_init(r2, ctx);
    nmod_mpoly_univar_init(ua, ctx); nmod_mpoly_univar_init(ub, ctx);

    nmod_mpoly_randtest_bounds(a, state, 81, bounds, ctx);
    nmod_mpoly_randtest_bounds(b, state, 81, bounds, ctx);

    /* eliminate y (variable 1): evaluation/interpolation in x */
    nmod_mpoly_resultant(r1, a, b, 1, ctx);

    /* the same resultant by subresultants over F_p[x] */
    nmod_mpoly_to_univar(ua, a, 1, ctx);
    nmod_mpoly_to_univar(ub, b, 1, ctx);
    nmod_mpoly_univar_resultant(r2, ua, ub, ctx);

    flint_printf("deg_y a = %wd, deg_x a = %wd\n", nmod_mpoly_degree_si(a, 1, ctx),
                 nmod_mpoly_degree_si(a, 0, ctx));
    flint_printf("deg_x res = %wd (bound %wd), equal: %d\n",
                 nmod_mpoly_degree_si(r1, 0, ctx),
                 nmod_mpoly_degree_si(b, 1, ctx) * nmod_mpoly_degree_si(a, 0, ctx)
                 + nmod_mpoly_degree_si(a, 1, ctx) * nmod_mpoly_degree_si(b, 0, ctx),
                 nmod_mpoly_equal(r1, r2, ctx));

    nmod_mpoly_univar_clear(ua, ctx); nmod_mpoly_univar_clear(ub, ctx);
    nmod_mpoly_clear(a, ctx); nmod_mpoly_clear(b, ctx);
    nmod_mpoly_clear(r1, ctx); nmod_mpoly_clear(r2, ctx);
    nmod_mpoly_ctx_clear(ctx);
    flint_rand_clear(state);
    return 0;
}
Output
deg_y a = 8, deg_x a = 8
deg_x res = 128 (bound 128), equal: 1

Use in FLINT#

Referenced from#

References#

  • [GG2003] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, second edition, Cambridge University Press (2003)
  • [BS2005] A. Bostan and É. Schost. Polynomial evaluation and interpolation on special sets of points. Journal of Complexity 21 (2005), 420–446.
  • [Col1971] Collins, George E. : The Calculation of Multivariate Polynomial Resultants, SYMSAC '71, ACM 1971 212–222
  • [Kro1882] L. Kronecker, "Grundzüge einer arithmetischen Theorie der algebraischen Grössen", Journal für die reine und angewandte Mathematik 92 (1882), 1–122
  • [HuMon2016] J. Hu and M. Monagan. A fast parallel sparse polynomial GCD algorithm. Proceedings of ISSAC 2016, ACM, 271–278; full version in Journal of Symbolic Computation 105 (2021), 28–63. https://doi.org/10.1016/j.jsc.2020.06.001
  • [Duc2000] L. Ducos. Optimizations of the subresultant algorithm. Journal of Pure and Applied Algebra 145 (2000), 149–163. https://doi.org/10.1016/S0022-4049(98)00081-4
  • [Vil2018] G. Villard. On computing the resultant of generic bivariate polynomials. Proceedings of ISSAC 2018, ACM, 391–398. https://doi.org/10.1145/3208976.3209020
Cite this page

The FLINT team, “Bivariate resultants by evaluation and interpolation,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/multivariate/modp-bivariate-resultant.html (generated 2026-11-20).