Bivariate resultants by evaluation and interpolation
- Cost
- operations in for points, where are the degrees in the eliminated variable and those in the other one.
Let have degrees and in and degrees , in . Their resultant with respect to is the determinant of the Sylvester matrix, a polynomial . The subresultant algorithm computes it by pseudo-remainder sequences in , whose intermediate coefficients have growing degree in . When is large enough, it is faster to evaluate at many points, compute univariate resultants over , 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 is an FFT prime.
Degree bound and specialisation#
Lemma 1 (Degree bound). .
Proof. The Sylvester matrix has rows of coefficients of (polynomials in of degree at most ) and rows of coefficients of (degree at most ). Every term of the expansion of the determinant is a product of one entry from each row.
Hence is determined by its values at distinct points, the number Collins [Col1971] takes for each variable in turn. The value at must be computed from the specialisations and , whose degrees may be lower than and when is a root of a leading coefficient.
Lemma 2 (Specialisation). Let , , , and , the leading coefficients of and in .
- If , then .
- If and , then .
- If both degrees drop, .
Here is the resultant of and with respect to their actual degrees, and is 0 if or is zero.
Proof. Evaluation commutes with the determinant, so is the determinant of the Sylvester matrix of and built with the formal degrees and . In case 1, the leading coefficients of in that matrix are zero, and expanding along the first columns, each of which then has the single nonzero entry , gives the formula. Case 2 follows from case 1 applied to , with the sign of the exchange for the actual degrees. In case 3, the first column of the matrix contains only .
Algorithm#
Input: with and a prime . Output: , or failure if is too small.
- Set .
- Choose distinct points: if FLINT has
fft_smalland is divisible by (an FFT prime), the powers of a primitive -th root of unity ; otherwise a geometric progression with of order at least , where is the first of that works. If , no such exists: fail. - Evaluate each of the coefficients of and (as polynomials in ) at the points, by FFTs or by the geometric progression algorithm [BS2005], in blocks of points sized to bound the memory.
- At each point, compute the univariate resultant of the specialisations with
_nmod_poly_resultantand apply Lemma 2. - Interpolate from its values, by an inverse FFT or geometric interpolation.
The evaluation of one coefficient of length at most at points of a geometric progression costs operations, so step 3 costs , step 5 costs , and step 4 costs univariate resultants of degree , each with the half-gcd algorithm (Half-GCD) or with Euclid's algorithm for small degrees. In the FFT case the points are split into cosets of the -th roots of unity, each evaluated by a substitution and one transform of length ; 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 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 , of degrees , in and , in . A ring homomorphism of the coefficient ring that keeps the leading coefficients in nonzero commutes with the resultant, since the resultant is a polynomial in the coefficients: . Three such maps reduce the problem to Algorithm 1.
- Monomial factors. If , then , and similarly for ; both are shifted down to their minimal exponent in each .
- Deflation. If every exponent of left in and is a multiple of , the map is injective and its inverse is applied to both.
- Kronecker substitution [Kro1882]. With one more than a bound on the degree in of the resultant of the shifted and deflated polynomials, the map with is injective on the polynomials of degree less than in each .
The resultant is then recovered from its image in by reading off the digits of each exponent of in the mixed radix , and Algorithm 1 needs points: exactly one per coefficient of the dense box of the resultant. The packed coefficients of and 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 , and let be the largest value of over the terms of (the other variables being ignored), and that over the terms of . Then
Proof. Row of the Sylvester matrix holds the coefficient of in in column , a polynomial of degree at most in , and row holds that of , of degree at most . 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 times the sum of the column indices, which is the right-hand side.
The weight gives as in Lemma 1, which is reached by polynomials dense in a box. The weight gives the Bézout bound when and have total degrees and in and the same degrees in : 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 , and only depends on the upper convex hull of the points , so its minimum is at or at a slope of that hull for or for ; FLINT takes the minimum over these. Since , the bound is at least and , so the substitution is also injective on and , and keeps their leading coefficients in nonzero.
The images of and have degree at most and in , so that the bound of Lemma 1 on the degree of their resultant is
with equality when every comes from the weight 0, and Algorithm 1 is told the number of points . Applied to the substitution for all at once, Lemma 3 also bounds the total degree of the resultant in the , 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 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 in turn is evaluated at 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 , 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 nonzero, so being injective on the resultant is enough.
Example#
Two random polynomials of degree 8 in each variable modulo the prime ; 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:
#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;
}deg_y a = 8, deg_x a = 8 deg_x res = 128 (bound 128), equal: 1
Use in FLINT#
nmod_mpoly_resultant_kroneckerapplies More variables: Kronecker substitution and then Algorithm 1 to polynomials in two or more variables with single-word exponents and positive degrees in the eliminated variable, packing the terms directly into the dense bivariate form; it declines when the dense form would have more than entries or points, or when is too small (Algorithm 1 fails).nmod_mpoly_resultantuses it when the dense form does not exceed the input by more than 64 times beyond entries and a gain is predicted. With a single variable packed into (the bivariate case), the inputs must not be tiny andn_bpoly_mod_resultant_cutoffmust predict a gain: , or with at least 4096 points. With two or more, both inputs must have at least 5 terms and , where is the smaller number of terms, the smaller length in , the number of points and the number of monomials of the box within the bound on the total degree: the subresultant algorithm pays for the terms of the resultant, and the dense algorithm for its whole box. Otherwise it uses the subresultant algorithm of Ducos [Duc2000] on the univariate forms (nmod_mpoly_univar_resultant)._n_bpoly_mod_resultant_multipointimplements Algorithm 1 onn_bpoly_t, taking the number of points from the caller. It is reached through_n_bpoly_mod_resultant_len(andn_bpoly_mod_resultant,_n_bpoly_mod_resultant), where the bivariate algorithm is chosen by the sizes for every dense bivariate resultant over : those of the Kronecker forms above, of the images modulo primes below and of the generic polynomial rings. Algorithm 1 is the only algorithm there so far; one added there, an algorithm of lower complexity at large degrees for instance [Vil2018], is used by all of these in its range.fmpz_mpoly_resultant_kroneckerapplies More variables: Kronecker substitution and then_fmpz_bpoly_resultant_len, which uses_n_bpoly_mod_resultant_lenmodulo many primes and combines the results by the Chinese remainder theorem (see fmpz_mpoly.h), up to entries and points.fmpz_mpoly_resultantuses it under the same conditions as over , except that with two or more variables packed it needs at least 4 terms and , the number of points mattering little against the coefficient growth of the subresultant algorithm.fmpq_mpoly_resultantgoes throughfmpz_mpoly_resultant.gr_poly_resultantover a polynomial ring overnmodpasses its arguments to_n_bpoly_mod_resultantwhenn_bpoly_mod_resultant_cutoffpredicts a gain, andgr_poly_resultant_multipointto_n_bpoly_mod_resultant_multipoint(the memory layouts ofgr_polyovernmodand ofn_bpolycoincide).
int nmod_mpoly_resultant(nmod_mpoly_t R, const nmod_mpoly_t A, const nmod_mpoly_t B, slong var, const nmod_mpoly_ctx_t ctx)int nmod_mpoly_resultant_kronecker(nmod_mpoly_t R, const nmod_mpoly_t A, const nmod_mpoly_t B, slong var, const nmod_mpoly_ctx_t ctx)int n_bpoly_mod_resultant(n_poly_t res, const n_bpoly_t A, const n_bpoly_t B, nmod_t mod)int n_bpoly_mod_resultant_cutoff(slong lenA, slong lenB, slong npoints)Referenced from#
- Multivariate polynomials: representations and algorithms (overview)
- Polynomial GCDs and resultants (overview)
fmpz_mpoly_resultant_kroneckerfmpz_bpoly_resultant,_fmpz_bpoly_resultant,_fmpz_bpoly_resultant_len_gr_poly_resultant_multipoint,gr_poly_resultant_multipoint,_gr_poly_resultant_modular,gr_poly_resultant_modular- mpoly.h (module)
mpoly_resultant_kronecker_set- nmod_mpoly.h (module)
nmod_mpoly_resultant_kroneckern_bpoly_mod_resultant,_n_bpoly_mod_resultant,_n_bpoly_mod_resultant_len,_n_bpoly_mod_resultant_multipoint,n_bpoly_mod_resultant_cutoff
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
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).
@misc{flint-doc-algorithms-multivariate-modp-bivariate-resultant,
author = {{The FLINT team}},
title = {{Bivariate resultants by evaluation and interpolation}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/multivariate/modp-bivariate-resultant.html},
note = {Generated 2026-11-20}
}