mpoly.h

Initialises ctx for nvars variables and the ordering ord. With nvars equal to zero the context describes constants; it then behaves like a degree ordering with one field that is always zero. An invalid ordering throws FLINT_ERROR.

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

Releases the context. The context owns no memory, so this does nothing, but it should be called for symmetry with mpoly_ctx_init.

Returns a random ordering.

Return whether the ordering of mctx is a degree ordering (ORD_DEGLEX or ORD_DEGREVLEX), respectively a reversed ordering (ORD_DEGREVLEX).

Prints lex, deglex or degrevlex to standard output.

Return the number N of words of a monomial packed with fields of bits bits. In the single precision case 1 \le \mathit{bits} \le FLINT_BITS this is \lceil \mathit{nfields} / \lfloor \text{FLINT\_BITS}/\mathit{bits} \rfloor \rceil (read from a table); in the multiprecision case bits must be a multiple of FLINT_BITS and N = \mathit{nfields} \cdot \mathit{bits} / \text{FLINT\_BITS}. The unsuffixed version dispatches on bits.

Rounds a required number of bits up to a valid packing width. For \mathit{bits} \le FLINT_BITS the result is the largest width that is at least MPOLY_MIN_BITS and at least bits and needs no more words than bits itself, so no space is wasted; for larger bits it is the next multiple of FLINT_BITS. For example, with three variables and lex ordering, any bits up to 21 is rounded to 21 on a 64-bit machine.

Sets (cmpmask, N) to the comparison mask for monomials packed with bits bits: zero for ORD_LEX and ORD_DEGLEX, and for ORD_DEGREVLEX all ones in every field except the total degree field. Two packed monomials compare in the monomial ordering as the multiword integers obtained by an exclusive or with this mask. Every function that compares monomials takes such a mask.

Returns the word with the high (guard) bit of each bits-bit field set, for \mathit{bits} \le FLINT_BITS. A packed word is valid if and only if its bitwise and with this mask is zero.

Return the number of bits needed to pack the user exponent vector user_exp, including the guard bit: one more than the bit length of the largest exponent, or of the total degree for degree orderings. The result is not rounded with mpoly_fix_bits. For _ui, a total degree that overflows a word gives 2*FLINT_BITS.

Returns the number of bits needed to pack the monomial x_v^e, that is 1 + \lceil \log_2(e + 1) \rceil.

Pack the user exponent vector exp2 into the monomial exp1 with bits bits per field, computing the total degree field for degree orderings. It is not checked that the exponents fit; use mpoly_exp_bits_required_ui and friends first.

Unpack the packed monomial poly_exps into the user exponent vector user_exps. The _sp versions require \mathit{bits} \le FLINT_BITS and the _mp versions a multiple of FLINT_BITS greater than FLINT_BITS; the unsuffixed versions dispatch. The _mp versions throw FLINT_ERROR if an exponent does not fit a ulong (respectively an slong).

Unpack the packed monomial poly_exps into a user exponent vector of fmpz, for any packing width.

Return the exponent of the variable of index var in the packed monomial poly_exps, without unpacking the other fields. The multiprecision versions throw FLINT_ERROR if the exponent does not fit the return type.

Convert an already unpacked array of nfields fields into a user exponent vector, by reordering the fields and dropping the total degree field. They are used together with mpoly_max_fields_fmpz to compute degrees. The _ui versions assume that the fields fit a ulong.

Pack len consecutive vectors of nfields fields from exp2 into exp1, with bits bits per field. In the single precision case the fields of one vector are written from the least significant bits of the first word up, starting a new word whenever the next field does not fit, and the unused high bits are zero. It is not checked that the fields fit.

Unpack len packed vectors of nfields fields of bits bits from exp2 into exp1. The _ui version requires the fields to fit a ulong.

Converts len monomials packed with bits2 bits per field in exps2 into monomials packed with bits1 bits in exps1, which must have room for len*mpoly_words_per_exp(bits1, mctx) words. Returns 1 for success. Widening always succeeds; narrowing returns 0 as soon as a field does not fit in bits1 - 1 bits, leaving exps1 partially written.

Helpers for algorithms that detect exponent overflow while producing their output. They replace *bits_ptr by mpoly_fix_bits(*bits_ptr + 1, mctx), update *N_ptr, and return a new array, allocated with flint_malloc with room for alloc monomials, containing the first len monomials of old_exps (packed with old_bits bits) repacked to the new width. old_exps is not freed. The second version also reallocates *cmpmask_ptr with flint_realloc and refills it, so it must have been allocated with flint_malloc.

Return whether every exponent of the monomial of index n in the array exps fits a ulong, respectively an slong.

Sets exp to a random user exponent vector that can be packed into exp_bits bits (including the guard bit), for testing.

Set a monomial to 1 (all fields zero), copy a monomial, swap two monomials. mpoly_monomial_set_extra copies exp3 and adds extra to the word of index offset.

Copies len monomials of N words. With GCC this is a macro for memcpy, so the arrays must not overlap.

Set exp_ptr to the product (sum of fields) or quotient (difference of fields) of the monomials exp2 and exp3. The plain versions work word by word and are for single precision fields; the _mp versions propagate carries across words and are for multiprecision fields. The caller is responsible for overflow (add) and for divisibility (sub).

Set exp1 to exp2 plus (minus) scalar times exp3, that is, to \mathit{exp2} \cdot \mathit{exp3}^{\pm \mathit{scalar}} as monomials; madd_inplace_mp adds to exp12. The _mp versions use mpn arithmetic over all N words.

Multiprecision versions of madd and msub with a scalar of scalar_limbs words (at most N) or a nonnegative fmpz, computed modulo 2^{N \cdot \text{FLINT\_BITS}}. exp1 must not alias exp3.

Set exp2 to the c-th power of the monomial exp3, that is, multiply every field by c. The plain version multiplies each word and is only correct if no field overflows; the _mp and fmpz versions multiply the N-word integer, which is correct for multiprecision fields. In mpoly_monomial_mul_fmpz, c \ge 0 must have at most N words.

Set exp1 to the field-wise maximum (least common multiple) or minimum (greatest common divisor) of exp2 and exp3. The single precision versions take the overflow mask and compute all fields of a word at once without branches: the guard bit of each field of mask + exp2 - exp3 records whether that field of exp2 is at least that of exp3.

Return whether a field of the monomial has its guard bit set, that is, whether an addition overflowed or a subtraction went negative. The single precision versions take the overflow mask; the _mp version tests the top bit of each multiword field.

Return whether the monomial exp3 divides exp2, and if so set exp_ptr to the quotient. If not, exp_ptr holds garbage.

Return whether exp3 divides exp2 without computing the quotient.

Return whether the monomial exp2 is a square, that is, every field is even, and if so set exp_ptr to its square root. The single precision versions shift whole words right by one bit, so that the low bit of each field lands in the guard bit of the field below, where the overflow test detects it.

Versions of the functions above that dispatch to the single precision or the _mp version according to bits, for code that handles both packing widths. The mask argument is only used in the single precision case. mpoly_monomial_valid_any_bits returns whether no guard bit is set; in builds with assertions the other functions assert that their inputs are valid.

Return whether a monomial is 1, whether two monomials are equal, and whether exp2 equals exp3 with extra added to its word of index offset.

Compare two packed monomials in the monomial ordering given by the mask from mpoly_get_cmpmask. mpoly_monomial_cmp returns 1, 0 or -1 as exp2 is greater than, equal to or less than exp3; mpoly_monomial_lt and mpoly_monomial_gt return whether their first argument is less, respectively greater, than the second.

Versions for one-word monomials: compare, a > b, a \ge b.

Compare the monomials as N-word unsigned integers, which is the monomial ordering for ORD_LEX and ORD_DEGLEX (and is used for lex orderings in internal code).

As the _nomask functions, comparing exp2 with exp3 plus extra added to the word of index offset. Used for recursive representations in which one variable is kept out of the packed monomial.

Compares two packed monomials with possibly different packing widths in the ordering of mctx, returning 1, 0 or -1.

Compares two arrays of length monomials lexicographically term by term, returning the comparison of the first pair that differs, or 0. The packing widths may differ.

Returns the index of the field that holds the exponent of the variable of index v: v for reversed orderings and nvars - 1 - v otherwise.

Set the nfields unpacked fields of the generator of index var.

Returns the number of bits needed to pack a generator, which is MPOLY_MIN_BITS.

For a single precision packing: set oneexp (or mexp) to the packed generator of index var, and set offset and shift such that the exponent of var in a packed monomial e is (e[offset] >> shift) with the low bits bits kept.

For a multiprecision packing: return the word offset of the field of var; the second version also sets mexp to the packed generator.

Returns whether the packed monomial exps is the generator of index var, or, if var is negative, whether it is any generator.

For a lex ordering and single precision packing, returns the exponents of the variables of index 0 and 1 in the monomial Aexps, packed into one word with pack_exp2.

Fill the matrix of a monomial substitution, used by the *_compose_*_gen functions and the matrix method of composition. M has mctxAC->nfields + 1 rows and mctxB->nfields columns; the column of a variable of B holds the unpacked fields of its image in the ring of A and C, and a 1 in the last row means that the variable is mapped to zero. The first function maps the variable of index i to the variable of index c[i] (or to zero if c[i] is negative or out of range). The second fills the column of Bvar with the monomial (Cexp, Cbits), or marks it as zero if Cexp is NULL.

Searches the sorted array (poly_exps, len) for the monomial exp by binary search. Returns 1 and sets index to its position if it is present; otherwise returns 0 and sets index to the position where it would have to be inserted to keep the array sorted, in [0, \mathit{len}].

Returns the index of the one-word monomial e in the array (Aexps, Alen) sorted in decreasing order as unsigned integers, or -1 if it does not occur.

Return the index of the monomial with user exponent vector exp (respectively the packed monomial Mexp packed with Mbits bits) in the sorted array (Aexp, Alength) packed with Abits bits, or -1 if it does not occur.

Set max_fields (min_fields) to the nfields unpacked field-wise maxima (minima) of the monomials. The _ui_sp versions require single precision packing. The minimum functions require \mathit{len} > 0; the maximum of an empty array is zero.

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

Set user_degs to the degree in each variable, all -1 if len is zero. The _si versions assume that the degrees fit an slong. The threaded version splits the array among the given thread pool handles.

Return or set the degree in the variable of index var (-1 if len is zero). For a lex ordering and var equal to 0 only the first monomial is read.

Compute the total degree, the maximum over the monomials of the sum of the exponents, which is -1 for an empty array. For degree orderings mpoly_total_degree_fmpz reads it from the degree field of the first monomial; mpoly_total_degree_fmpz_ref always scans all monomials and serves as a reference implementation for testing. mpoly_total_degree_si assumes that the result fits.

For each variable of index i that occurs with a positive exponent in one of the monomials, sets used[i] to a nonzero value. Other entries are left unchanged, so the results for several arrays can be combined.

Returns whether no variable other than the one of index var occurs in the monomials.

Consistency checks used by the assert_canonical functions. The first returns whether every total degree field (for degree orderings) equals the sum of the exponents, the second whether some field has its guard bit set, and the third whether the monomials are strictly decreasing.

Sets Aexp to the monomials of Bexp in reverse order. In place operation is allowed.

For each variable v, with S_v the set of exponents of v in the monomials, sets shift[v] to \min S_v and stride[v] to \gcd\{e - \min S_v : e \in S_v\}, which is zero if S_v has one element. Every monomial then has exponent \mathit{shift}_v + k \cdot \mathit{stride}_v in v. For an empty array 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 of the monomials Bexps, writing the result to Aexps with Abits bits, which must be large enough. When deflating, a zero stride maps the exponent to zero, and every e - \mathit{shift}_v must be divisible by the stride. The order of the monomials may change.

Divide (shift right) or multiply (shift left) every monomial in place by x_{\mathit{var}}^{\mathit{amount}}, without changing the packing width. The division must be exact and the product must fit; _mpoly_gen_shift_right and _mpoly_gen_shift_left require single precision packing.

Divide every monomial in place by the monomial with user exponent vector user_exps, which must divide all of them.

Sets var_powers to the user exponent vector of the greatest common divisor of the monomials (\mathit{Alen} > 0) and divides every monomial by it in place.

For a lex ordering and single precision packing, partition the sorted monomials into runs with the same exponent of the variable of index 0 (respectively the same exponents of the variables of index 0 and 1). The array (*Dcoeffs, *Dlen) receives the start index of each run, and is reallocated as needed (*Dalloc is its allocation) so that (*Dcoeffs)[*Dlen] equals Alen.

Convert monomials between a context Bctx with n variables and a lex context Actx with m \le n variables, both with single precision packing. Deflation sets the exponent of variable k of A to (e_l - \mathit{shift}_l)/\mathit{stride}_l where l = \mathit{perm}[k] and e_l is the exponent of variable l of B; inflation is the inverse, setting the exponents of variables of B not in the image of perm to their shift. The GCD and factoring code use these to move to a lex ordering in the variables that actually occur. The order of the monomials is not maintained; the caller sorts afterwards.

Convert len one-word monomials between the usual packing with bits bits per field and the tight packing with the bases mults (the first entry corresponding to the least significant field). Only the least significant num fields are converted; each must be less than its base.

Returns whether the tightly packed monomial e2 divides e1. The array (prods, num + 1) holds the partial products 1, b_0, b_0 b_1, \ldots of the bases.

Sets max_exp to the maximum of each of the num fields over the tightly packed monomials (exps, len), with prods as for mpoly_monomial_divides_tight.

Split one-word monomials (Aexp, Alen) by the value of their most significant field (the main variable for lex, the total degree for degree orderings), which takes at most l1 values. The array ind of length \mathit{l1} + 1 receives the start of each chunk, and pexp the remaining num fields of each monomial in tight packing with the bases mults (for lex) or all equal to deg (for degree orderings, where the lowest field is dropped because the total degree determines it). Used by the array multiplication.

Given one-word monomials (exp1, len1) with fields of bits bits, sets the l1 start indices i1 and lengths n1 (which may be zero) of the chunks of monomials with exponent \mathit{l1} - 1, \mathit{l1} - 2, \ldots, 0 in the field of index k - 1, which must be the most significant nonzero field. The fields are not masked.

Pack two (three) small exponents into one word with fields of \text{FLINT\_BITS}/2 (\text{FLINT\_BITS}/3) bits, e0 in the most significant field, so that comparing the words compares the exponent tuples lexicographically. extract_exp returns the field of index idx (counted from the least significant) of a word packed with nvars equal fields. Used for the bivariate and trivariate base cases of the GCD and factoring code.

Insert the chain node x with monomial exp into the heap. The entry of index 0 is unused, so *heap_len is one more than the number of entries. If an entry with the same monomial is found at the top, at index *next_loc, or on the path from the insertion point to the root, x is chained to it (and *next_loc remembers its position); otherwise a new entry is created and *heap_len is incremented. _mpoly_heap_insert returns 1 if a new entry was created and 0 if the node was chained. The one-word version takes maskhi = cmpmask[0]. Initialise *next_loc to a value larger than any heap length.

Remove the entry with the largest monomial and return its chain (cast to void *), decrementing *heap_len. The heap must not be empty.

Splits the products of two sorted monomial arrays for parallel multiplication. Finds a monomial e such that the number of products a_i b_j \le e is between lower and upper (or as close as possible), stores this number in e_score, and sets *e_ind to one of the work arrays t1, t2, t3 (each of length a_len): entry i of it is the first index j with a_i b_j \le e. Assumes that 1 is the smallest monomial.

Returns m with 0 \le m < n such that (m + 1)/(n - m) is close to \mathit{la}/\mathit{lb}: the number of threads (besides the calling one) to give to the first of two independent tasks of sizes la and lb when n threads are available.

Initialise an empty tree with data blocks of data_size bytes, or free it. Clearing does not clear the data blocks themselves.

Return a pointer to the data block for key, inserting a new node if the key is not present; *its_new is set to whether this happened (the new block is uninitialised). The pointer is valid until the next insertion.

Return the index of the root node, from which the tree can be traversed through the left and right fields of the nodes.

Initialise for \mathit{nvars} > 0 variables, and free.

For each variable, sets the maximal and minimal exponent in the monomials (Aexps, Alength) (\mathit{Alength} > 0, single precision packing) and the number of monomials attaining each.

For each variable v, sets strides[v] to the GCD of all e - \min_A for exponents e of v in A and all e - \min_B for exponents in B, given the limits computed by mpoly_gcd_info_limits. Deflating by these strides does not change the GCD.

Sets Iv->mvars to the number of variables that occur in A (after the monomial content is removed, they occur in both), initialises the variable permutations of all algorithms to these variables in their natural order, sets the densities (the number of terms divided by the product of the deflated degrees plus one) and clears can_use.

Returns the number of interpolation steps in the variable of index var of the Brown permutation after which Brown's algorithm should stop attempting early divisibility tests, or 0 if the degree bounds of Iv are not reliable.

Decide whether an algorithm is applicable and, if so, set its bit in Iv->can_use, choose its variable order and estimate its cost. Brown and Hensel need at least two variables whose dense representations fit, and their cost is modelled from the products of the degrees of G, A/G and B/G; Zippel chooses as main variable one with few leading and trailing terms; the Berlekamp–Massey based method (measure_bma, used for MPOLY_GCD_USE_ZIPPEL2) needs at least three variables and chooses two main variables of small degree that fit in half a word. measure_zippel2 is the analogue for the Zippel2 variant used by the nmod and fq_nmod modules.

Tests whether two monomial arrays of the same length differ by a monomial factor term by term up to a common monomial, that is, whether A = a \cdot H and B = b \cdot H term by term for monomials a, b with \gcd(a, b) = 1. If so, sets Abarexps and Bbarexps to the user exponent vectors of a and b and returns 1; otherwise returns 0. Used to detect GCDs whose cofactors are monomials.

Tries to prove that a polynomial with monomials (Aexps, Alen) is not a square, using t (N words) as scratch space. Returns 1 if the field-wise maximum of the monomials is not a square monomial, that is, some variable (or, for degree orderings, the total degree) has odd maximal degree, since the degrees of a square are even. Returns 0 if this test is inconclusive, and for an empty array.

Initialise and free.

Computes a compression of the polynomial with monomials (Aexps, Alen) (single precision packing): a unimodular change of exponents e = V e' + D after which the exponents e' are nonnegative and the polynomial depends on as few variables with as small degrees as the heuristic finds, and tests irreducibility from the Newton polytope.

The core of mpoly_compression_set: given the l \times n exponent matrix S (rows are monomials, l > 1), finds a unimodular n \times n matrix V, a vector D and new exponents (overwriting S) with V S'_i + D = S_i for every row, \min_i S'_{ij} = 0 and deg[j] one more than the maximum of column j, by greedy unimodular column operations that reduce the product of the degrees. Returns the number of columns of S' that are not identically zero, which come first.

Try to prove that a polynomial with the given monomials is absolutely irreducible from its Newton polytope alone, independently of the coefficients, following Gao and Lauder [GaoLau2001]. The exponents are projected onto random planes, and the projection of the polytope is tested for integral indecomposability, at most tries_left times. Return 1 if irreducibility was proved and 0 if not; a return of 0 says nothing. The underscore version takes the exponent matrix with row stride stride; the public version returns 0 for multiprecision packing or fewer than two terms.

For f \in F[y][x] of degree n - 1 in x, transforms the input l_i = 1 + \deg_y(\operatorname{coeff}(f, x^i)) for 0 \le i < n into bounds l_i > \deg_y \operatorname{coeff}(f g_x/g, x^i) valid for every divisor g of f, using the upper convex hull of the points (i, l_i). These logarithmic derivative bounds are used by the bivariate factoring code over finite fields.

Reallocates the slong array *array with allocation *alloc to hold at least len entries, growing geometrically.

Allocate and initialise an element of R, and clear and free it.

Memory management: initialise (with room for len terms), clear, swap, and ensure room for len terms.

Sets G to the last nonzero subresultant of B and A, computed with Ducos' algorithm [Duc2000], which divides out the predictable factors of the subresultant sequence early. Requires \deg B \ge \deg A \ge 0 and nonzero inputs; A and B are destroyed. Returns 0 if a ring operation failed (for example an exponent overflow in a power), 1 otherwise.

Set r to the resultant of f and g, respectively d to the discriminant of f, using the subresultant algorithm; the inputs are destroyed. The resultant of a zero polynomial is zero, the discriminant of a constant a is 1/a^2 (so it can fail), and the discriminant of a linear polynomial is 1. Return 1 for success and 0 if a ring operation failed.

Initialise and free a parser. The ring E->R must be set before the first use.

Adds the name s with value v (an element of E->R, copied). Terminals are kept sorted by decreasing length, so that the longest matching name is used.

Parses the string (s, len) and sets res to its value, returning 0 for success and -1 for failure; on failure res holds an unspecified value. The grammar is described at fmpz_mpoly_set_str_pretty: nonnegative integer constants, terminals, +, - (binary and unary), *, / (exact division), ^ followed immediately by a nonnegative integer, parentheses and spaces.