nmod_mpoly.h

Initialises ctx for polynomials in nvars variables with the monomial ordering ord, one of ORD_LEX, ORD_DEGLEX and ORD_DEGREVLEX (see mpoly.h), and coefficients modulo n = modulus. The modulus must be at least 1.

Initialises ctx with a random number of variables in [0, max_nvars] and a random ordering, and the given modulus. Used for testing.

Replaces the modulus of ctx by modulus, keeping the variables and the ordering. Polynomials of the context must be reduced modulo the new modulus before they are used with it.

Return the number of variables, the monomial ordering and the modulus of ctx.

Frees the memory used by ctx. Polynomials of the context must be cleared first.

Initialise A as the zero polynomial. nmod_mpoly_init allocates nothing; nmod_mpoly_init2 allocates space for alloc terms with the minimum exponent field width MPOLY_MIN_BITS, and nmod_mpoly_init3 space for alloc terms with bits bits per exponent field.

Frees the memory used by A.

nmod_mpoly_fit_length ensures that A has space for at least len terms, growing the allocation at least geometrically. nmod_mpoly_realloc changes the allocation to exactly alloc terms, which must be at least the current length; with alloc = 0 it frees the memory and sets A to zero.

Ensure space for len terms with exponent fields of bits bits. nmod_mpoly_fit_length_fit_bits repacks the existing exponents if bits exceeds A->bits; nmod_mpoly_fit_length_reset_bits sets A->bits to bits and leaves the exponent data undefined, for use before overwriting all terms.

Reduces the length of A to newlen if it is longer, keeping the newlen leading terms. The result is canonical.

Set A to B (resp. modify A) with the exponents repacked into fields of Abits bits. Return 1 for success and 0 if some exponent does not fit into Abits bits, in which case A is set to zero.

Returns a string representing A, such as x^2*y+4*x+3, which the caller must free with flint_free. Terms appear in the order of the context and coefficients as integers in [0, n).

Print A in the format of nmod_mpoly_get_str_pretty to file or to stdout. The return value is positive on success and negative on failure.

Sets A to the polynomial in the null-terminated string str, written with integers, the variable names x, parentheses and the operators +, -, *, / and ^ (followed by a nonnegative integer exponent). Integers are reduced modulo n. A division must be exact, which allows division by invertible constants. Returns 0 on success; returns -1 and sets A to zero if the string cannot be parsed or a division is not exact.

Sets A to the variable of index var.

If var \ge 0, returns whether A is the variable of index var; if var < 0, returns whether A is any variable. For n = 1 every polynomial is zero, and so equal to every variable.

Set A to B, and swap A and B efficiently.

Returns whether A and B are equal.

nmod_mpoly_is_ui returns whether A is a constant (including zero). nmod_mpoly_get_ui returns the value of the constant A, and throws if A is not constant.

Set A to the constant c \bmod n.

Set A to 0 or to 1.

Return whether A equals the constant c \bmod n, zero or one.

Set the array degs to the degrees of A in each variable; nmod_mpoly_degrees_fit_si returns whether all of them fit an slong, which nmod_mpoly_degrees_si requires.

Return or set deg to the degree of A in the variable of index var. The slong version requires the degree to fit.

Return or set td to the total degree of A; nmod_mpoly_total_degree_fits_si returns whether it fits an slong.

Sets used[i] to a nonzero value if the variable of index i appears in A and to zero otherwise, for each variable.

Get or set the coefficient of A at the monomial M, which must be a monomial with any nonzero coefficient (otherwise the function throws). Setting a coefficient to zero removes the term.

Get or set the coefficient of the monomial with exponent vector exp (one entry per variable). Setting to zero removes the term, setting a new monomial inserts it in its place. Each call costs time linear in the length of A; use nmod_mpoly_push_term_ui_ui to build polynomials term by term.

Return the coefficient of the monomial with exponent vector exp, as nmod_mpoly_get_coeff_ui_ui and nmod_mpoly_get_coeff_ui_fmpz (older names).

Sets C to the coefficient of \prod_i x_{v_i}^{e_i} in A viewed as a polynomial in the variables x_{v_i} with coefficients in the other variables, where v_i = vars[i] and e_i = exps[i] for 0 \le i < length. The variables must be distinct, and 0 < length \le m. The result does not involve the variables in vars.

Returns the leading coefficient of A, which must be nonzero.

Returns whether A involves no variable other than the one of index var.

If B is a polynomial in the variable of index var only, set A to it as a univariate polynomial and return 1; otherwise return 0. A must have the same modulus as the context.

Set A to the univariate polynomial B in the variable of index var.

Returns 1, -1 or 0 according as A is greater than, less than or equal to B in some total order on polynomials that is fixed for the context. For monomials it agrees with the monomial ordering of the context.

Returns a pointer to the coefficient of the term of index i.

nmod_mpoly_is_canonical returns whether A is in canonical form (sorted, no zero coefficients, reduced coefficients, valid exponent packing). nmod_mpoly_assert_canonical throws if it is not.

Returns the number of terms of A, which for canonical A is the number of nonzero coefficients.

Sets the length of A to new_length, deleting terms from the end or appending terms with zero coefficient and zero exponent.

Get or set the coefficient of the term of index i. Setting a zero coefficient makes A non-canonical.

Return whether all exponents of the term of index i fit a ulong (resp. an slong).

Set exp to the exponent vector of the term of index i. The ulong and slong versions throw if an exponent does not fit.

Return the exponent of the variable of index var in the term of index i, throwing if it does not fit.

Set the exponent vector of the term of index i, which usually makes A unsorted.

Set M to the term of index i, or to its monomial with coefficient 1.

Append a term with coefficient c \bmod n and exponent vector exp to A, in constant amortised time. The _ffmpz version takes the exponents as an array of fmpz, the _fmpz version as an array of pointers to fmpz. After all terms are pushed, call nmod_mpoly_sort_terms and nmod_mpoly_combine_like_terms unless they were pushed in decreasing order with distinct monomials and nonzero coefficients.

Sorts the terms of A into the order of the context, without combining equal monomials or removing zero coefficients, by a radix sort in time linear in the size of A.

Combines adjacent terms with equal monomials and removes zero coefficients. If A is sorted, the result is canonical.

Sets A to B with the order of its terms reversed, which is not canonical unless B has at most one term.

Set A to a random polynomial with at most length terms and random coefficients, with the exponents of each variable in [0, exp_bound), of the variable of index i in [0, exp_bounds[i]), or of at most exp_bits bits.

Set A to B + c or B - c, with c reduced modulo n.

Set A to B + C or B - C.

Sets A to -B.

Set A to c B. nmod_mpoly_scalar_mul_nmod_invertible requires c to be reduced and invertible modulo n, so that no coefficient can vanish.

Sets A to B + d C.

Sets A to B divided by its leading coefficient. Throws if B is zero or its leading coefficient is not invertible.

Sets A to the derivative of B with respect to the variable of index var. In characteristic p the terms whose exponent in that variable is divisible by p disappear.

Returns the value of A at the point whose coordinates are the entries of vals, one per variable, which must be reduced modulo n.

Sets A to B with the variable of index var replaced by the constant val.

Sets A to B evaluated at the univariate polynomials C[0], C[1], ..., one per variable of the context. Returns 1 for success and 0 if the result would be too large to compute.

Set A to B evaluated at the polynomials C[0], C[1], ..., one per variable of ctxB, where A and the C[i] belong to ctxAC. A must not alias B or any C[i]. Return 1 for success and 0 if the result would be too large to compute. If every C[i] is zero or a monomial with coefficient 1, nmod_mpoly_compose_nmod_mpoly only transforms the exponent vectors by a matrix; otherwise it uses a Horner scheme (if some C[i] has more than one term) or a geobucket sum of the powered terms.

Sets A to B with the variable of index i in ctxB replaced by the variable of index c[i] in ctxAC, or by zero if c[i] is negative. The array c has one entry per variable of ctxB, and nonnegative entries must be valid variable indices of ctxAC.

Sets A to B C. For short inputs it uses nmod_mpoly_mul_johnson. For larger inputs with one word per exponent it tries Kronecker substitution (nmod_mpoly_mul_dense) if the product is dense enough, then the array method (nmod_mpoly_mul_array) for 2 to 7 variables if the array is not too large and sparse, and otherwise the heap method; the array and heap methods use several threads when the inputs have more than about 512 terms per thread.

Set A to B C by Johnson's heap algorithm [Joh1974], which merges the products b_i C with a heap of size \min(\mathrm{len}(B), \mathrm{len}(C)) and costs O(\mathrm{len}(B) \mathrm{len}(C) \log \min(\mathrm{len}(B), \mathrm{len}(C))) monomial comparisons. The first version uses one thread, the second the available threads.

Try to set A to B C by accumulating the products in a dense array indexed by the exponents (by the exponents bounded by the degrees for ORD_LEX, by the total degree for the degree orderings). Return 0 without changing A if the array would be too large or the exponents need more than one word. The first version uses one thread.

Try to set A to B C by Kronecker substitution into univariate polynomials and nmod_poly_mul. Returns 0 if the dense representation would be too large.

Set A to B^k, with B^0 = 1 (zero if n = 1). nmod_mpoly_pow_fmpz throws if k < 0, and returns 0 (failure) if k does not fit an slong and B has more than one term; otherwise both return 1. For a prime modulus p \le 99999, nmod_mpoly_pow_ui writes k = \sum_j k_j p^j and uses B^{p^j} = B(x_0^{p^j}, \ldots), so that only the powers B^{k_j} with k_j < p are computed by repeated multiplication.

If B divides A, sets Q to the exact quotient A/B and returns 1; otherwise sets Q to zero and returns 0. Throws FLINT_DIVZERO if B is zero and A is not (unless n = 1), and FLINT_IMPINV if the leading coefficient of B is not invertible. For long A the heap division runs in several threads.

Sets Q to A/B, assuming that the division is exact; throws if it is not.

Variants of nmod_mpoly_divides. The first uses the heap algorithm of Monagan and Pearce [MonPea2011] in one thread, which stops as soon as a remainder term cannot be divided. nmod_mpoly_divides_dense uses Kronecker substitution and univariate division; it returns -1 if the dense representation would be too large, and otherwise 0 or 1 as nmod_mpoly_divides.

As nmod_mpoly_divides, using the heap and the available threads; the underscore version takes the thread handles. Only declared when the configuration knows that the target is strongly ordered (the macro nmod_mpoly_divides_heap_threaded is then defined); in that case nmod_mpoly_divides already uses it for large inputs.

Set Q and R to the quotient and the remainder of the division of A by B with respect to the monomial ordering: A = QB + R where no term of R is divisible by the leading monomial of B. nmod_mpoly_div only computes Q; when the division is known to be exact it is faster than nmod_mpoly_divides.

Divides A by the len polynomials B[0], ..., B[len-1]: sets the quotients Q[i] and the remainder R with A = R + \sum_i Q_i B_i, where no term of R is divisible by the leading monomial of any B_i. At each step the leading remainder term is divided by the first B_i whose leading monomial divides it. The result depends on the order of the divisors unless they form a Gröbner basis.

The heap implementations [MonPea2011] of nmod_mpoly_div, nmod_mpoly_divrem and nmod_mpoly_divrem_ideal, which those functions call.

If A = Q^2 for some Q, set Q to such a square root and return 1; otherwise return 0 (and set Q to zero). nmod_mpoly_is_square only returns whether A is a square. The modulus must be prime. For odd p the root is computed term by term with a heap, as for division; for p = 2, A is a square exactly when all its exponents are even, and the root is obtained by halving them. Even moduli other than 2 throw FLINT_IMPINV.

If Q^2 + AQ = B has a solution, sets Q to a solution and returns 1; otherwise returns 0. The modulus must be prime. For odd p this completes the square; in characteristic 2, where that is impossible, the equation is solved term by term (Quadratics).

Sets M to the GCD of the terms of A: zero if A is zero, and otherwise the monomial with coefficient 1 whose exponent in each variable is the minimum over the terms of A.

Sets g to the GCD of the coefficients of A viewed as a polynomial in the vars_length variables vars[i] with coefficients in the other variables, and returns 1 for success. The result does not involve the variables in vars.

Set G to the monic GCD of A and B; the GCD of zero and zero is zero. nmod_mpoly_gcd_cofactors also sets \bar{A} = A/G and \bar{B} = B/G. Return 1 for success and 0 for failure, in which case the outputs are undefined. The algorithm is chosen from the shapes and estimated densities of the inputs; over small fields the evaluation-based algorithms work with images over extension fields.

Set G to the monic GCD of A and B by one algorithm: Brown's dense interpolation, Hensel lifting, Zippel's sparse interpolation in one main variable, or sparse interpolation with two main variables and the leading coefficient known in advance. Return 0 if the algorithm cannot be applied or fails. The trivial cases (monomials, missing variables, univariate inputs) are handled first, as in nmod_mpoly_gcd.

For each variable v, let S_v be the set of its exponents in A. Sets shift[v] to \min S_v and stride[v] to \gcd \{ e - \min S_v : e \in S_v \}. If A is zero, all shifts and strides are zero.

nmod_mpoly_deflate replaces each exponent e of the variable v by (e - shift[v])/stride[v] (which must be exact), with the convention that a zero stride gives 0. nmod_mpoly_inflate applies e \mapsto shift[v] + stride[v] e. Shifts and strides must be nonnegative. Deflating by the values of nmod_mpoly_deflation and inflating gives back the polynomial.

Sets R to the resultant of A and B with respect to the variable of index var, that is, the determinant of their Sylvester matrix as polynomials in that variable. Returns 1 for success. The modulus must be prime. For polynomials in exactly two variables of sufficient size the resultant is computed by evaluating the other variable at many points and interpolating (Bivariate resultants by evaluation and interpolation); otherwise by the subresultant algorithm of Ducos on the univariate forms.

Sets R to the discriminant of A with respect to the variable of index var, and returns 1 for success. The modulus must be prime.

Initialise, clear, allocate space for length terms, swap, and set to zero.

nmod_mpoly_to_univar sets A to B viewed as a polynomial in the variable of index var. nmod_mpoly_from_univar converts back; its result is undefined if the coefficients of B involve that variable.

Return whether the degree in the main variable fits an slong, the number of terms, and the exponent of the term of index i.

Set c to (resp. swap c with) the coefficient of the term of index i.

Sets the coefficient of x_v^e to c, inserting or removing a term as needed.

Sets Gx to a GCD of Ax and Bx up to a factor that does not involve the main variable, computed by the subresultant pseudo-remainder sequence of Ducos. Returns 1 for success. The modulus must be prime.

Set R to the resultant of Ax and Bx, and D to the discriminant of Fx, with respect to the main variable, by subresultants. Return 1 for success. The modulus must be prime.

Print A as a sum of terms (c)*X^e, the coefficients c with the variable names x and the main variable as X; and throw if A is not canonical.

Ensures that the coefficient array coeffs (with allocation coeffs_alloc) has room for length coefficients and the exponent array exps (with allocation exps_alloc) room for length exponent vectors of N words, growing them at least geometrically.

Sets the length field of A to newlen, which must not exceed the allocation.

Merge the sorted term arrays of lengths len2 and len3 (with N words per exponent and comparison mask cmpmask) into coeff1, exp1, adding or subtracting coefficients modulo fctx, and return the length of the result. The output must have room for len2 + len3 terms.

Sort the terms left to right - 1 of A by a most-significant-bit radix sort starting at bit pos, for one-word exponents (with masks cmpmask and totalmask) or exponents of N words.

Append a term with exponent vector exp and undefined coefficient to A, repacking A if the exponent needs more bits.

Versions of nmod_mpoly_set_coeff_ui_fmpz and nmod_mpoly_get_term_ui_fmpz that take the exponents as an array of fmpz.

Sets A to the product of the term arrays (coeff2, exp2, len2) and (coeff3, exp3, len3), with N words of bits-bit fields per exponent, by Johnson's heap algorithm, and returns the length of the product.

The multiplication methods behind nmod_mpoly_mul, given the maximum exponent fields of the inputs (computed with mpoly_max_fields_fmpz) and, for the threaded versions, the thread handles. The array and dense versions return 0 if they cannot be applied.

Kernels of the array multiplication: the products are accumulated chunk by chunk in arrays of one, two or three words per coefficient, which are reduced modulo n when a chunk is complete.

Set A to B^k by repeated multiplication; the underscore version works on a term array and uses T as scratch space.

Exact division with the given thread handles, and the heap exact division of term arrays used by nmod_mpoly_divides_monagan_pearce, which returns 0 if the division is not exact.

Evaluates the polynomial given by the term arrays at the point alphas.

Return whether raising a univariate polynomial of the given length to the power e would exceed the addressable memory; used by the composition functions.

Sets A to B with each exponent vector multiplied by the matrix M (with one more row than the number of fields of ctxAC), which implements substitutions of monomials for variables.

Conversions between nmod_mpoly and univariate polynomials in the variable of index var, with given exponent bits, shifts and strides.

Version of nmod_mpoly_from_univar producing exponents of Abits bits.

Throws if some term of r is divisible by the leading monomial of g; used in tests of nmod_mpoly_divrem.

Sets up the generic ring interface R (used by the parser and the subresultant code in mpoly) for polynomials of the context.

Initialise an empty geobucket, free it, and make room for i buckets.

nmod_mpoly_geobucket_set sets B to p, swapping p into a bucket (so p is changed). nmod_mpoly_geobucket_add and nmod_mpoly_geobucket_sub add or subtract p, and nmod_mpoly_geobucket_empty sets p to the sum and empties B.

Memory management and basic operations of dense polynomials. The set_degbounds functions set the degree bounds and allocate the coefficient array, returning 0 if its size would overflow.

Conversions between sparse and dense polynomials, used by nmod_mpoly_divides_dense.

Memory management, assignment, printing and access for nmod_mpolyu_t. _nmod_mpolyu_get_coeff returns the coefficient of x^{\mathit{pow}}, inserting a zero term if necessary, and nmod_mpolyu_leadcoeff the leading coefficient of the leading coefficient.

Arithmetic on nmod_mpolyu_t: shifting the main exponents by s, scaling, the GCD of the coefficients (returning 1 for success), exact division and multiplication by a polynomial in the other variables, exact division with nmainvars main variables, and copying the monomial structure ("form") of B into A with undefined coefficients, as needed by sparse interpolation.

Conversions between the representations. The perm_deflate functions permute the variables by perm, deflate their exponents by shift and stride and convert into a context uctx, lctx or nctx with lexicographic ordering; the perm_inflate functions undo this with Abits-bit exponents.

Memory management, assignment and inspection of nmod_mpolyn_t. nmod_mpolyn_lastdeg returns the degree in the last variable, which is the variable of the n_poly_t coefficients.

Arithmetic on nmod_mpolyn_t: scaling, multiplication and exact division by univariate polynomials in the last variable, the GCD of the n_poly_t coefficients, and exact division (returning 1 if it is exact).

The same operations for nmod_mpolyun_t.

For A in a lexicographic context, viewed as a polynomial in the first num_vars variables: set c to its leading coefficient, and g to the GCD of its coefficients (returning 1 for success).

Initialise and clear a stack, and change its context. The fit_request functions ensure that k more objects of a kind are available and return a pointer to them, the request functions also reserve them, take_top reserves one previously fitted object, give_back releases the k most recent objects, and size returns the number of reserved objects.

Reinterpret an nmod_poly_struct as an n_poly_struct, whose first three fields have the same layout.

Compute the GCD G and, when Abar and Bbar are not NULL, the cofactors of the nonzero A and B, using the algorithms in the bit mask algo (MPOLY_GCD_USE_BROWN, MPOLY_GCD_USE_HENSEL, MPOLY_GCD_USE_ZIPPEL, MPOLY_GCD_USE_ZIPPEL2, or MPOLY_GCD_USE_ALL). The _small version requires exponents of at most FLINT_BITS bits. Return 1 for success.

Brown's dense algorithm on nmod_mpolyn_t inputs: evaluation of the variable of index var at points of \mathbb{F}_p (smprime), or reduction modulo irreducible polynomials of increasing degree in it (lgprime), recursion, and interpolation with a degree-based termination test. Return 1 for success, also setting the cofactors.

Zippel's sparse interpolation on nmod_mpolyu_t inputs. gcdp works with evaluation points in \mathbb{F}_p, gcds solves for the coefficients of an assumed monomial structure f by evaluating var variables and returns a status code (nmod_gcds_ret_t) that distinguishes success from bad evaluation points and a wrong form, and gcdm first tries gcdp and then falls back to images over \mathbb{F}_p[x_{m-1}]/(f) for irreducible f of increasing degree.

Sparse interpolation with two main variables (the algorithm of nmod_mpoly_gcd_zippel2), given degree bounds and the leading coefficient gamma of the GCD, over \mathbb{F}_p or over extension fields.

GCD by Hensel lifting of a bivariate image factorisation A = G \bar{A}, B = G \bar{B} (with G of degree Gdeg in the main variable), with evaluation points in \mathbb{F}_p or in an extension \mathbb{F}_{p^k} with p^k < 10^6.

Heuristics of the two-variable sparse interpolation: decide which of the GCD and the cofactors to interpolate, from their estimated degrees and sizes.