fmpz_mpoly.h

Initialises ctx for the ring \mathbb{Z}[x_0, \ldots, x_{\mathit{nvars}-1}] with the monomial ordering ord, which is one of ORD_LEX, ORD_DEGLEX and ORD_DEGREVLEX.

Initialises mctx with a random ordering and a random number of variables between 0 and max_nvars, for testing.

Return the number of variables and the ordering of ctx.

Releases any memory used by ctx. Polynomials must be cleared before their context.

Initialises A as the zero polynomial, without allocating memory, with exponents packed into MPOLY_MIN_BITS bits.

Initialise A as zero with room for alloc terms, with exponents packed into MPOLY_MIN_BITS bits, respectively into bits bits. bits must be a valid packing width (see mpoly_fix_bits).

Changes the allocation of A to alloc terms. Terms beyond alloc are discarded, which can leave a polynomial that is not the truncation of interest but is still canonical. With alloc equal to zero, A is freed and reinitialised.

Ensures that A has room for at least len terms, at least doubling the allocation when it grows, so that appending terms one by one costs amortised constant time per term.

Ensures that the exponents of A are packed with at least bits bits, repacking the existing terms if necessary. bits must be a valid packing width.

Ensures room for len terms with exponents packed into bits bits and sets A->bits to bits. The value of A is destroyed (its monomials are not repacked); the caller writes new terms and sets the length.

Frees the memory used by A.

Set the length of A to newlen, demoting the coefficients that are dropped so that no memory is held by them. _fmpz_mpoly_set_length requires newlen to be at most the allocation and may also increase the length; fmpz_mpoly_truncate only decreases it, keeping the first newlen terms.

Versions of fmpz_mpoly_realloc and fmpz_mpoly_fit_length for raw arrays of coefficients and of monomials of N words, with allocation *Aalloc. New coefficients are zero.

Return a string such as 3*x^2*y-y+1 representing A (respectively the terms (poly, exps, len) packed with bits bits), terms in the order in which they are stored. The string must be freed with flint_free.

Print A in the format of fmpz_mpoly_get_str_pretty to standard output or to file. The return value is that of the underlying output functions (positive on success).

Sets A to the polynomial given by the expression str in the variables named by x, and returns 0, or returns -1 if the string cannot be parsed. The expression may contain nonnegative integer constants, the variable names, +, - (binary or unary), *, /, ^, parentheses and spaces. Division must be exact, and ^ must be followed immediately by a nonnegative integer exponent; powers associate to the left. Implicit multiplication such as 2x is not supported. Variable names are matched greedily, longest first. On failure the value of A is unspecified.

Sets poly to the variable of index i.

Returns whether poly is the variable of index k, or, if k is negative, whether it is any variable.

Set A to B. The underscore version copies n terms with monomials of N words between raw arrays.

Return whether A and B are equal. The polynomials may be packed with different widths. The underscore version compares n terms with monomials of N words.

Swaps A and B in constant time.

Returns the maximum bit length b of the absolute values of the coefficients of A, as b if all coefficients are nonnegative and as -b otherwise.

Returns whether every coefficient of the array is a small fmpz (not an mpz), that is, has at most SMALL_FMPZ_BITCOUNT_MAX bits. Products of two such coefficients fit in two words, and sums of up to 2^{\mathtt{FLINT\_BITS}/4} or so of them in three, which the heap algorithms exploit.

Returns whether A is a constant (including zero).

Sets c to the constant A. Throws FLINT_ERROR if A is not constant.

Set A to the constant c.

Set A to 0, respectively 1.

Return whether A equals the constant c.

Return whether A is 0, respectively 1.

Returns whether the degree of A in each variable fits an slong.

Set degs[i] to the degree of A in the variable of index i. The _si version requires the degrees to fit an slong.

Set or return the degree of A in the variable of index var.

Test whether the total degree of A fits an slong, and set or return it. For degree orderings it is read from the first term; for lex all terms are scanned.

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

Set or return the coefficient of the monomial with exponent vector exp (zero if it does not occur). The _ui and _si return values are only meaningful if the coefficient fits.

Set the coefficient of the monomial with exponent vector exp to c, inserting a term, changing one, or removing one if c is zero, so that A stays canonical. The packing width of A grows if needed. The underscore version takes the exponents as a flat fmpz array.

Get or set the coefficient of the monomial of the one-term polynomial M (its coefficient is ignored). Throw FLINT_ERROR if M does not have exactly one term.

Sets C to the coefficient of \prod_k x_{\mathit{vars}[k]}^{\mathit{exps}[k]} in A viewed as a polynomial in the variables vars with coefficients in the other variables: the sum of the terms of A whose exponents in these variables are exactly exps, divided by that monomial. The arrays have length entries, with 0 < \mathit{length} \le nvars and distinct variables.

Returns 1, 0 or -1 according to an arbitrary but fixed total order on polynomials: first by length, then by the monomials of the terms in order, then by the coefficients. For two monomials with the same coefficient this agrees with the monomial ordering.

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

Sets A to B as a univariate polynomial in the variable of index var, and returns 1. Returns 0 if B involves another variable or a degree does not fit an slong.

Set the multivariate polynomial to the univariate polynomial B (or pol) in the variable of index v (or var). The second version throws if the context has no variables.

Sets A to \sum_i \mathit{Bcoeffs}[i] x_{\mathit{var}}^i with exponents packed into Abits bits, which must be large enough for the degree \mathit{Blen} - 1.

For a context with exactly one variable, sets A to \sum_{i \le \mathit{Adeg}} \mathit{Acoeffs}[i] x^i with at least Aminbits bits per field. The coefficients Acoeffs are moved into A and cleared, so the array must not be used afterwards.

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

Test whether A is canonical: no coefficient is zero, the monomials are strictly decreasing, and the packed exponents are valid (no guard bit set, and for degree orderings the total degree field is correct). The assert version throws FLINT_ERROR with a message describing the problem instead of returning 0.

Return a pointer to the coefficient of term i, respectively of the leading term (term 0) of the nonzero polynomial A. The index is only checked in builds with assertions.

Sets the length of A to new_length: terms are removed from the end, or terms with zero coefficient and monomial 1 are appended (which makes the polynomial noncanonical until they are filled in).

Set or return the coefficient of term i. The _ui and _si results are only meaningful if the coefficient fits.

Set the coefficient of term i to c. A zero coefficient is stored as such.

Return whether every exponent of term i fits an slong, respectively a ulong.

Set exp to the exponent vector of term i. With exponents packed into more than one word per field, the _ui and _si versions throw if an exponent does not fit.

Return the exponent of the variable of index var in term i. They throw if the exponent does not fit the return type.

Set the monomial of term i to the exponent vector exp, repacking A if it does not fit. The terms may no longer be in order afterwards.

Set M to term i of A, respectively to its monomial with coefficient 1.

Append the term c x^{\mathit{exp}} to A in amortised constant time, repacking A if the exponents do not fit. Nothing else is done: the result is canonical only if the terms are appended in decreasing order with distinct monomials and nonzero coefficients. Otherwise call fmpz_mpoly_sort_terms and fmpz_mpoly_combine_like_terms after the last term.

Append a term with monomial exp and an unspecified coefficient, which the caller then sets through A->coeffs + A->length - 1.

Sorts the terms of A into decreasing order of their monomials. Like terms are not combined and zero coefficients are not removed. The sort is a most significant bit first radix sort on the packed monomials, which costs O(\mathit{len} \cdot b) for b significant bits of the monomials.

The recursive steps of fmpz_mpoly_sort_terms: sort the terms of index in [\mathit{left}, \mathit{right}) by the bits of their monomials at positions \mathit{pos}, \mathit{pos} - 1, \ldots, 0, assuming the higher bits are equal. The first version is for one-word monomials and skips the bit positions not set in totalmask.

Adds up adjacent terms with equal monomials and removes terms with zero coefficient, in linear time. If the terms are sorted, the result is canonical.

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

Set A to a random polynomial with at most length terms (fewer after like terms are combined), coefficients of about coeff_bits bits (as from fmpz_randtest), and exponents in [0, \mathit{exp\_bound}), in [0, \mathit{exp\_bounds}[i]) for the variable of index i, or such that the monomials can be packed into exp_bits bits. Intended for testing.

Set A to B + c, respectively B - c. Only the constant term changes, so with A aliased to B this costs constant time.

Set A to B + C, respectively B - C, by merging the sorted term lists in time linear in the total length.

Merge two sorted term lists with monomials of N words packed with the same width into (poly1, exps1), which must have room for \mathit{len2} + \mathit{len3} terms and must not overlap the inputs, and return the length of the result.

Sets A to -B.

Set A to c B.

Sets A to c B + e D in one pass over both polynomials.

Set A to B/c for a nonzero c that divides every coefficient of B. This is not checked; if the division is not exact the result is meaningless.

If the nonzero integer c divides every coefficient of B, set A to B/c and return 1; otherwise set A to zero and return 0.

Sets A to the partial derivative of B with respect to the variable of index var.

Sets A and scale such that A = \mathit{scale} \int B \, dx_v with respect to the variable x_v of index var (with zero constant of integration), where \mathit{scale} > 0 is the least positive integer for which this has integer coefficients.

Sets ev to A(\mathit{vals}[0], \ldots, \mathit{vals}[n-1]). The powers of each value are computed by repeated squaring once, and each term is evaluated with them. Returns 1 for success and 0 for failure.

Return or set the value of A \bmod n at the point alphas, whose entries must be reduced modulo the modulus n of fpctx.

Sets res to the value of pol at the complex ball vector x (one entry per variable) at precision prec, by direct term evaluation for at most 6 terms and a Horner scheme otherwise; the result is indeterminate if the evaluation fails.

Sets A to B with the variable of index var replaced by val. Returns 1 for success and 0 for failure.

Sets A to B(C_0, \ldots, C_{n-1}) for univariate polynomials C_i, one per variable of ctxB. Returns 1 for success and 0 for failure.

Set A to B(C_0, \ldots, C_{n-1}), where B belongs to ctxB and A and the n polynomials C_i (one per variable of ctxB) belong to ctxAC. A must not alias B or any C_i. Return 1 for success and 0 for failure. If every C_i is zero or a monomial with coefficient 1, fmpz_mpoly_compose_fmpz_mpoly maps the exponents by a matrix (_fmpz_mpoly_compose_mat) and cannot fail; otherwise it uses the Horner method if some C_i has more than one term and the geobucket method otherwise. The geobucket version computes powers of the C_i and sums the terms in a geobucket; the Horner version evaluates a recursive Horner scheme.

Sets A to B with the variable of index i of ctxB replaced by the variable of index c[i] of ctxAC, or by zero if c[i] is negative. Each nonnegative c[i] must be less than the number of variables of ctxAC. This renames, permutes, merges or drops variables at the cost of mapping and sorting the monomials. A may alias B if the contexts are the same.

Sets A to the image of B under the monomial map given by the matrix M, as filled by mpoly_compose_mat_gen or mpoly_compose_mat_fill_column: each unpacked monomial of B is multiplied by M, terms whose image has a nonzero last entry are dropped, and the result is sorted and combined. A must not alias B.

Return whether raising an integer of bbits bits to the power e \ge 0 should be refused because the result would have about WORD_MAX/16 bits or more.

Sets A to B C. The algorithm (Johnson's heap method, an array method or a dense Kronecker substitution, possibly with threads) is chosen from the lengths, degrees and ordering of the inputs. See Multiplication.

Set A to B C by Johnson's heap method [Joh1974], which works for any inputs and uses memory proportional to the input and output. The first version uses one thread; the second divides the output among the available threads [MonPea2009].

Try to set A to B C by accumulating the products in a dense array, one slice of the main variable (lex) or of the total degree (degree orderings) at a time. Return 0, leaving A unchanged, if the inputs do not have one-word monomials or the array would be too large. The first version uses one thread.

Tries to set A to B C by Kronecker substitution into a univariate product computed by fmpz_poly_mul. Returns 0 if the exponents of an input do not fit a word or the dense size of the product overflows.

Sets A to B C where C has exactly one term, in linear time.

The heap multiplication on raw term lists: multiply (poly2, exp2, len2) by (poly3, exp3, len3) (both nonzero, monomials of N words packed with bits bits, which must suffice for the product), writing the product to (*poly1, *exp1) with allocation *alloc, which are reallocated as needed, and return its length. The heap has at most len2 entries, so the shorter input should come first. No aliasing is allowed. The maxfields version takes precomputed field-wise maxima of the inputs (and clobbers maxBfields), chooses the packing width and handles aliasing.

Threaded heap multiplication with the given thread pool handles (and the calling thread) and precomputed field maxima; maxBfields is clobbered.

Array multiplication for lex and for degree orderings, single threaded or with a thread pool, given the field-wise maxima of the nonzero inputs, which must have one-word monomials. Return 0 without changing A if the array would be too large: for lex the main variable must have degree less than 300 in the product and the other variables must span at most 300000 array entries; for degree orderings d^{n-1} \le 300000 where d is one more than the total degree of the product.

Dense multiplication given the field-wise maxima of the nonzero inputs, which must have single precision exponents. Returns 0 if the dense representation does not fit.

Set A to B^k and return 1, or return 0 if the result would be unreasonably large. For k \ge 3 the power is computed by the Monagan–Pearce FPS algorithm (fmpz_mpoly_pow_fps); squares are computed by multiplication. fmpz_mpoly_pow_ui fails when k (\mathit{len}(B) - 1) exceeds about WORD_MAX/16. fmpz_mpoly_pow_fmpz throws for negative k, and for k that does not fit an slong succeeds only if B is zero or a monomial with coefficient \pm 1.

Sets A to B^k for nonzero B and k \ge 2 by the FPS algorithm of Monagan and Pearce [MonPea2012], a heap-based sparse version of the recurrence obtained from B (B^k)' = k B' B^k, which computes the terms of B^k and B^{k-1} in order using O(k \cdot \mathit{len}(B) \cdot \mathit{len}(B^k)) monomial operations in the worst case but far fewer coefficient operations than repeated multiplication. See Squaring and powering.

If B divides A exactly, sets Q to A/B and returns 1; otherwise sets Q to zero and returns 0. Throws FLINT_DIVZERO if B is zero. Uses heap division, threaded for large dividends.

Sets Q to A/B, throwing FLINT_ERROR if the division is not exact.

Sets Q and R such that A = QB + R, by the division algorithm in which each quotient coefficient is the floor quotient of the current coefficient by \operatorname{lc}(B). A term of R whose monomial is divisible by \operatorname{lm}(B) has a coefficient with the sign of \operatorname{lc}(B) and absolute value less than |\operatorname{lc}(B)|. If \operatorname{lc}(B) = \pm 1 this is the usual multivariate division with remainder.

Sets Q to the quotient of fmpz_mpoly_divrem, without computing the remainder. It is much faster than fmpz_mpoly_divides when the division is known to be exact.

Set scale, Q and R such that \mathit{scale} \cdot A = QB + R and no monomial of R is divisible by \operatorname{lm}(B), where \mathit{scale} > 0 is the least positive integer for which this division over \mathbb{Z} is possible (a divisor of a power of \operatorname{lc}(B)). The second version does not compute R.

Versions of fmpz_mpoly_divrem and fmpz_mpoly_quasidivrem for a list of len divisors B_i: set the quotients Q_i and the remainder R with (\mathit{scale} \cdot) A = \sum_i Q_i B_i + R, by the multivariate division algorithm that reduces each leading term by the first divisor whose leading monomial divides it.

Exact division testing by the heap algorithm of Monagan and Pearce [MonPea2007], single threaded, respectively with threads [MonPea2010]. The threaded version, and the threaded path of fmpz_mpoly_divides, only exist if FLINT was configured for a machine with a strongly ordered memory model (FLINT_KNOW_STRONG_ORDER); test with #ifdef fmpz_mpoly_divides_heap_threaded.

Exact division testing by a dense array method: returns 1 and sets poly1 to the quotient if it is exact, 0 if it is not, and -1 without a result if the array method does not apply (the exponents need more than one word, the ordering is ORD_DEGREVLEX, or the array would have more than 300000 entries). It is efficient for dense inputs.

The heap algorithms behind fmpz_mpoly_divrem and fmpz_mpoly_div.

Division with remainder as in fmpz_mpoly_divrem by a dense array method. Returns 0 without a result if the array would be too large or the exponents do not fit one word, and 1 otherwise.

The heap algorithms behind fmpz_mpoly_quasidivrem and fmpz_mpoly_quasidiv. They throw FLINT_DIVZERO if the divisor is zero.

The heap algorithms behind fmpz_mpoly_divrem_ideal and fmpz_mpoly_quasidivrem_ideal, with one heap for all divisors.

Exact division of nonzero raw term lists with monomials of N words packed with bits bits: writes the quotient to (*poly1, *exp1) with allocation *alloc, reallocating as needed, and returns its length if the division is exact and 0 otherwise. No aliasing is allowed.

Division as in fmpz_mpoly_div and fmpz_mpoly_divrem on raw nonzero term lists. They return the length of the quotient, and the second sets *lenr to the length of the remainder. No aliasing is allowed.

Division by len divisors on raw term lists; exp3[i] holds the monomials of poly3[i] repacked to bits bits. Returns the length of the remainder.

Array division on raw term lists with one-word monomials in num fields of bits bits, using the bases mults for the tight packing of the array index. The first returns the length of the quotient if the division is exact and 0 otherwise; the second returns the length of the quotient and sets *lenr. No aliasing is allowed.

Chooses the monomial boundaries at which the dividend is split among nworkers threads in the threaded exact division, storing them as the monomials of S. Returns nonzero if it detects on the way that the division cannot be exact. It is also used by nmod_mpoly.

If poly2 is the square of a polynomial, sets q to the square root with positive leading coefficient and returns 1; otherwise sets q to zero and returns 0. The terms of the root are computed in order with a heap, as in division [MonPea2011]. With check equal to 0 the input is assumed to be a square and the remaining terms are not verified, which saves time but gives a meaningless result for non-squares.

fmpz_mpoly_sqrt_heap with checking, and a test whether poly2 is a square (which computes the root).

The square root on raw term lists with monomials packed with bits bits; returns the length of the root, or 0 if the input is not a square.

Sets M to the GCD of the terms of A: the monomial whose exponents are the minimal exponents of A, with coefficient the content (GCD of the coefficients) of A, which is positive. If A is zero, so is M.

Sets res to f divided by the content of its coefficients, with the sign chosen so that the leading coefficient is positive. Zero stays zero.

Sets g to the GCD of the coefficients of A viewed as a polynomial in the variables listed in vars (with coefficients in \mathbb{Z} and the other variables), and returns 1, or returns 0 if a GCD computation failed. On success g does not involve the variables vars. Throws if a variable index is out of range. With no variables, g = A.

Tries to set G to the GCD of A and B, normalised to have a positive leading coefficient, and returns 1, or returns 0 if no algorithm succeeded (which does not happen in practice). The GCD of zero and zero is zero. See Greatest common divisors.

As fmpz_mpoly_gcd, and also sets \bar A = A/G and \bar B = B/G. If A and B are zero, all three outputs are zero; if only A is zero, G = \pm B, \bar A = 0 and \bar B = \pm 1. The three outputs must be distinct.

Try to compute the GCD with one specific algorithm, after the same preprocessing as fmpz_mpoly_gcd (which may solve easy cases directly): Brown's dense modular algorithm, Hensel lifting (EEZ-GCD), the subresultant pseudo-remainder sequence in a well chosen main variable, Zippel's sparse modular algorithm, and the sparse algorithm based on Berlekamp–Massey interpolation of Hu and Monagan. They return 0 if the algorithm is not applicable or fails, for example fmpz_mpoly_gcd_zippel2 with fewer than three variables. Intended for testing and benchmarking.

For each variable v, with S_v the set of exponents of v in A, sets shift[v] to \min S_v and stride[v] to \gcd\{e - \min S_v : e \in S_v\} (zero if S_v has one element). If A is zero, all shifts and strides are zero.

Apply e \mapsto (e - \mathit{shift}[v])/\mathit{stride}[v] (deflate) or e \mapsto \mathit{shift}[v] + \mathit{stride}[v] \, e (inflate) to the exponent of each variable v. Shifts and strides must be nonnegative. When deflating, every e - \mathit{shift}[v] must be a nonnegative multiple of the stride, and a zero stride requires e = \mathit{shift}[v], which is mapped to zero; deflating with the output of fmpz_mpoly_deflation therefore always works, and inflating undoes it.

Initialise as zero, free, ensure room for length terms, swap in constant time, and set to zero.

Sets A to B written as a polynomial in the variable of index var.

Set A to the polynomial \sum_i B_i x_{\mathit{var}}^{e_i}. The coefficients of B must not involve the variable var. The underscore version packs the result into Abits bits, which must suffice.

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

Return whether the degree fits an slong, the number of terms, and the exponent of term i (which must fit).

Set c to, respectively swap c with, the coefficient of term i.

Print A with the main variable written X and the coefficients in the variables x, and check that the exponents are strictly decreasing and the coefficients nonzero and canonical (throwing otherwise).

Sets gx to the last nonzero subresultant of ax and bx (Ducos' algorithm), a pseudo-GCD: a multiple of their GCD by an element of the coefficient ring. Requires \deg \mathit{ax} \ge \deg \mathit{bx} and nonzero inputs. Returns 1 for success and 0 for failure.

Set d to the resultant of ax and bx, respectively the discriminant of fx, in the main variable, by the subresultant algorithm. Return 1 for success and 0 for failure.

Sets R to the resultant of A and B with respect to the variable of index var, and returns 1, or returns 0 on failure. If the context has two variables and the inputs are dense enough and of large enough degree, the resultant is computed by a dense multimodular algorithm (fmpz_bpoly_resultant, which uses the evaluation and interpolation algorithm of Bivariate resultants by evaluation and interpolation modulo each prime); otherwise by Ducos' subresultant algorithm on the univariate forms [Duc2000].

Sets R to the discriminant of A with respect to the variable of index var, (-1)^{d(d-1)/2} \operatorname{res}(A, A')/\operatorname{lc}(A) up to the convention for low degrees used by mpoly_univar_discriminant, and returns 1, or returns 0 on failure.

Set res to the elementary symmetric polynomial e_k in all variables, respectively in the n distinct variables of indices vars: the sum of all products of k distinct variables. e_0 = 1, and e_k = 0 for k > n.

Initialise vec as a vector of len zero polynomials, and free it.

Prints the vector as [f0, f1, ...] with the default variable names.

Swap two vectors, ensure room for len entries, copy, and change the length (truncating, or appending zero polynomials).

Append a copy of f. fmpz_mpoly_vec_insert_unique appends it only if it is not already present (by linear search) and returns its index.

Sets vec to len random nonzero polynomials generated by fmpz_mpoly_randtest_bound with the given parameters.

Sets G to the primitive parts of the nonzero entries of F, without duplicates, in an unspecified order.

Sets res to the S-polynomial of f and g, scaled to integer coefficients: with L = \operatorname{lcm}(\operatorname{lm} f, \operatorname{lm} g) and c = \operatorname{lcm}(\operatorname{lc} f, \operatorname{lc} g), \frac{cL}{\operatorname{lt} f} f - \frac{cL}{\operatorname{lt} g} g.

Sets res to the primitive part of the remainder of f on division by the polynomials Iv (fmpz_mpoly_quasidivrem_ideal).

Returns whether G is a Gröbner basis (all S-polynomials reduce to zero) and, if F is not NULL, whether every element of F reduces to zero modulo G, so that G is a Gröbner basis of the ideal generated by F if G is contained in it.

Test whether the vector is autoreduced (inter-reduced): no term of an element is divisible by the leading monomial of another element; and set H to the autoreduction of F. The groebner version assumes that G is a Gröbner basis and produces the reduced Gröbner basis, which is unique up to the order of the entries.

Set G to a Gröbner basis of the ideal generated by F, by Buchberger's algorithm [Buc1965] with the usual criteria to skip pairs, following [BW1993]. The second version gives up and returns 0 if the basis gets longer than ideal_len_limit, a polynomial longer than poly_len_limit, or a coefficient larger than poly_bits_limit bits; G then generates the ideal but need not be a Gröbner basis. It returns 1 on success.

Fills R with the function pointers of the ring \mathbb{Z}[x_0, \ldots, x_{n-1}], for the generic code in mpoly.

For a lex context and 0 < \mathit{num\_vars} < n, view A \ne 0 as a polynomial in x_0, \ldots, x_{\mathit{num\_vars}-1} with coefficients in the other variables, and set c to its leading coefficient, respectively g to the GCD of its coefficients (returning 0 if a GCD failed). The outputs must not alias A and have the packing width of A.

Convert between a polynomial in the single variable var and a univariate polynomial with a shift: the first sets poly1 and *poly1_shift so that poly2 equals \mathit{poly1}(x) x^{\mathit{shift}} (it throws for multiprecision exponents), and the second sets poly1 to \mathit{poly2}(x_{\mathit{var}}) x_{\mathit{var}}^{\mathit{shift2}}.

Convert between a polynomial whose exponents are \mathit{shift} + k \cdot \mathit{stride} in each variable, with only var varying, and a univariate polynomial in k. Used by the GCD code.

Set A to B (or change A in place) with exponents packed into Abits bits, and return 1, or return 0 if the exponents do not fit, leaving A unchanged. The first rounds Abits with mpoly_fix_bits; the second requires a valid width.

Set max to the largest absolute value of a coefficient of A, and sum to the sum of the absolute values.

Initialise a cache for the powers of val, and free it.

Set a to b v^k, extending the cache for k \le 100 and computing the power directly for larger k, and return 1; the fmpz version returns 0 if the power cannot be computed.

Initialise a geobucket with value zero, free it, and make sure it has at least i (zeroed) levels.

Set the value of B to p, add p to it, subtract p from it, and move the value to p, leaving B zero. The first three functions take p over (its value is destroyed).

Initialise, ensure room for len coefficients, and free.

The array multiplication proper: split both inputs into chunks by the main variable (lex, with array bases mults) or by total degree (degree orderings, with base degb), and compute the chunks of the product one after another, each in a dense array, with coefficients accumulated in one, two or three words when a bound on their size allows it.

Add the products of all pairs of terms of the two term lists, whose monomials are tightly packed array indices, to the dense array poly1, with coefficients of one, two or three words (two's complement), or of type fmpz. The inputs are processed in blocks for cache locality.

As the addmul functions, subtracting; the _1 versions subtract the product of a single term d \cdot \mathit{exp2} with a term list. Used by the array division.

Append the nonzero entries of a dense coefficient array (one chunk of a product: main variable or total degree top) to P in decreasing monomial order, starting at term index Plen, clear the array, and return the new length. sm1, sm2 and sm3 arrays hold one, two or three words per coefficient.