utils_flint.h – extra methods for Flint types

General methods for multivariate polynomials

void fmpz_mpoly_primitive_part(fmpz_mpoly_t res, const fmpz_mpoly_t f, const fmpz_mpoly_ctx_t ctx)

Sets res to the primitive part of f, obtained by dividing out the content of all coefficients and normalizing the leading coefficient to be positive. The zero polynomial is unchanged.

void fmpz_mpoly_symmetric_gens(fmpz_mpoly_t res, ulong k, slong *vars, slong n, const fmpz_mpoly_ctx_t ctx)

void fmpz_mpoly_symmetric(fmpz_mpoly_t res, ulong k, const fmpz_mpoly_ctx_t ctx)

Sets res to the elementary symmetric polynomial \(e_k(X_1,\ldots,X_n)\).

The gens version takes \(X_1,\ldots,X_n\) to be the subset of generators given by vars and n. The indices in vars start from zero. Currently, the indices in vars must be distinct.

type fmpz_mpoly_vec_struct

type fmpz_mpoly_vec_t

A type holding a vector of fmpz_mpoly_t.

fmpz_mpoly_vec_entry(vec, i)

Macro for accessing the entry at position i in vec.

void fmpz_mpoly_vec_init(fmpz_mpoly_vec_t vec, slong len, const fmpz_mpoly_ctx_t ctx)

Initializes vec to a vector of length len, setting all entries to the zero polynomial.

void fmpz_mpoly_vec_print(const fmpz_mpoly_vec_t vec, const fmpz_mpoly_ctx_t ctx)

Prints vec to standard output.

void fmpz_mpoly_vec_swap(fmpz_mpoly_vec_t x, fmpz_mpoly_vec_t y, const fmpz_mpoly_ctx_t ctx)

Swaps x and y efficiently.

void fmpz_mpoly_vec_fit_length(fmpz_mpoly_vec_t vec, slong len, const fmpz_mpoly_ctx_t ctx)

Allocates room for len entries in vec.

void fmpz_mpoly_vec_set(fmpz_mpoly_vec_t dest, const fmpz_mpoly_vec_t src, const fmpz_mpoly_ctx_t ctx)

Sets dest to a copy of src.

void fmpz_mpoly_vec_append(fmpz_mpoly_vec_t vec, const fmpz_mpoly_t f, const fmpz_mpoly_ctx_t ctx)

Appends f to the end of vec.

slong fmpz_mpoly_vec_insert_unique(fmpz_mpoly_vec_t vec, const fmpz_mpoly_t f, const fmpz_mpoly_ctx_t ctx)

Inserts f without duplication into vec and returns its index. If this polynomial already exists, vec is unchanged. If this polynomial does not exist in vec, it is appended.

void fmpz_mpoly_vec_set_length(fmpz_mpoly_vec_t vec, slong len, const fmpz_mpoly_ctx_t ctx)

Sets the length of vec to len, truncating or zero-extending as needed.

void fmpz_mpoly_vec_randtest_not_zero(fmpz_mpoly_vec_t vec, flint_rand_t state, slong len, slong poly_len, slong bits, ulong exp_bound, fmpz_mpoly_ctx_t ctx)

Sets vec to a random vector with exactly len entries, all nonzero, with random parameters defined by poly_len, bits and exp_bound.

void fmpz_mpoly_vec_set_primitive_unique(fmpz_mpoly_vec_t res, const fmpz_mpoly_vec_t src, const fmpz_mpoly_ctx_t ctx)

Sets res to a vector containing all polynomials in src reduced to their primitive parts, without duplication. The zero polynomial is skipped if present. The output order is arbitrary.

Ideals and Gröbner bases

The following methods deal with ideals in \(\mathbb{Q}[X_1,\ldots,X_n]\). We use primitive integer polynomials as normalised generators in place of monic rational polynomials.

void fmpz_mpoly_spoly(fmpz_mpoly_t res, const fmpz_mpoly_t f, const fmpz_mpoly_t g, const fmpz_mpoly_ctx_t ctx)

Sets res to the S-polynomial of f and g, scaled to an integer polynomial by computing the LCM of the leading coefficients.

void fmpz_mpoly_reduction_primitive_part(fmpz_mpoly_t res, const fmpz_mpoly_t f, const fmpz_mpoly_vec_t vec, const fmpz_mpoly_ctx_t ctx)

Sets res to the primitive part of the reduction (remainder of multivariate quasidivision with remainder) with respect to the polynomials vec.

int fmpz_mpoly_vec_is_groebner(const fmpz_mpoly_vec_t G, const fmpz_mpoly_vec_t F, const fmpz_mpoly_ctx_t ctx)

If F is NULL, checks if G is a Gröbner basis. If F is not NULL, checks if G is a Gröbner basis for F.

int fmpz_mpoly_vec_is_autoreduced(const fmpz_mpoly_vec_t F, const fmpz_mpoly_ctx_t ctx)

Checks whether the vector F is autoreduced (or inter-reduced).

void fmpz_mpoly_vec_autoreduction(fmpz_mpoly_vec_t H, const fmpz_mpoly_vec_t F, const fmpz_mpoly_ctx_t ctx)

Sets H to the autoreduction (inter-reduction) of F.

void fmpz_mpoly_vec_autoreduction_groebner(fmpz_mpoly_vec_t H, const fmpz_mpoly_vec_t G, const fmpz_mpoly_ctx_t ctx)

Sets H to the autoreduction (inter-reduction) of G. Assumes that G is a Gröbner basis. This produces a reduced Gröbner basis, which is unique (up to the sort order of the entries in the vector).

pair_t fmpz_mpoly_select_pop_pair(pairs_t pairs, const fmpz_mpoly_vec_t G, const fmpz_mpoly_ctx_t ctx)

Given a vector pairs of indices \((i, j)\) into G, selects one pair for elimination in Buchberger’s algorithm. The pair is removed from pairs and returned.

void fmpz_mpoly_buchberger_naive(fmpz_mpoly_vec_t G, const fmpz_mpoly_vec_t F, const fmpz_mpoly_ctx_t ctx)

Sets G to a Gröbner basis for F, computed using a naive implementation of Buchberger’s algorithm.

int fmpz_mpoly_buchberger_naive_with_limits(fmpz_mpoly_vec_t G, const fmpz_mpoly_vec_t F, slong ideal_len_limit, slong poly_len_limit, slong poly_bits_limit, const fmpz_mpoly_ctx_t ctx)

As fmpz_mpoly_buchberger_naive(), but halts if during the execution of Buchberger’s algorithm the length of the ideal basis set exceeds ideal_len_limit, the length of any polynomial exceeds poly_len_limit, or the size of the coefficients of any polynomial exceeds poly_bits_limit. Returns 1 for success and 0 for failure. On failure, G is a valid basis for F but it might not be a Gröbner basis.

Index pairs

type pair_t

A pair of slong indices a and b.

type pairs_struct

type pairs_t

A type holding a vector of pair_t.

void pairs_init(pairs_t vec)

Initializes vec for use, setting it to the empty vector of pairs.

void pairs_fit_length(pairs_t vec, slong len)

Allocates space for len elements in vec.

void pairs_clear(pairs_t vec)

Frees vec.

void pairs_append(pairs_t vec, slong i, slong j)

Appends the pair \((i, j)\) to the end of vec.

void pairs_insert_unique(pairs_t vec, slong i, slong j)

Inserts \((i, j)\) without duplication into vec. If this pair already exists, vec is unchanged. If this pair does not exist in vec, it is appended.