gr_ore_poly.h

Returns a random Ore algebra type, favouring the derivative and the forward shift, for testing.

Initialise ctx as the ring of Ore polynomials over base_ring with the predefined algebra which_algebra, acting on the generator with index base_var of the base ring. These are for the algebras without parameters; the q-shift and Mahler algebras have their own constructors. The two functions are the same.

Initialise ctx for the q-shift algebra \sigma(a)(x) = a(qx) with q an element of the base ring (GR_UNABLE unless the base ring is a univariate polynomial ring), or the Mahler algebra \sigma(a)(x) = a(x^b) with b = mahler_base (GR_DOMAIN for b = 0).

gr_ore_poly_ctx_init_custom initialises ctx with a user-defined algebra: sigma_delta computes \sigma and \delta (see gr_ore_poly_sigma_delta), and ore_data is a pointer to data for it, which sigma_delta can retrieve with gr_ore_poly_ctx_data_ptr(ctx). The data is not freed by gr_ore_poly_ctx_clear.

Initialise ctx with a random algebra over base_ring, or (the second function) over a random base ring that it initialises in base_ring, for testing.

Clears the context and the algebra data it owns.

Set the name of the generator D to s (respectively s[0]), and set vec to the generators of the base ring (as constant Ore polynomials) followed by D.

Context methods. Whether the ring is a ring, the zero ring or thread-safe is inherited from the base ring; commutativity and the absence of zero divisors are currently reported as T_UNKNOWN.

Initialise poly as zero (with space for len coefficients), and clear it.

Return a pointer to the coefficient of D^i, and the length.

Swap two Ore polynomials in constant time, and make res a shallow copy of x sharing its coefficients.

Ensure space for len coefficients, set the length without normalising, and remove provably zero leading coefficients, as the gr_poly functions of the same names.

Set res to a copy of src, or to src with the terms of order newlen and higher removed.

Set poly to 0, 1, -1 or the generator D.

Set poly to a constant converted into the base ring. The function gr_ore_poly_set_other accepts an Ore polynomial with the same context (copied), an element of the base ring, an element of the coefficient ring of the base ring when the base ring is a univariate polynomial ring, or an integer or rational number (fmpz and fmpq contexts), each giving a constant; it returns GR_UNABLE for any other ring.

Comparisons, decided coefficientwise in the base ring. The underscore version requires \mathit{len1} \ge \mathit{len2}.

Write the Ore polynomial as an expression in the generator name of the context, with the coefficients on the left of the powers of D, to a stream, to a new string (to be freed with flint_free), or to standard output.

Parse an Ore polynomial from an expression in the generator name of the context and the generator names of the base ring; products are evaluated in the Ore algebra, so D*x and x*D differ. The underscore version writes exactly len coefficients (zero-padding) and returns GR_UNABLE if the result is longer; intermediate results may be longer.

Set poly to a random Ore polynomial of length at most len (respectively a random length below 5), for testing.

Compute \sigma(a) and \delta(a), or one of them, by calling the function stored in the context.

The functions implementing \sigma and \delta for the predefined algebras, with the signature gr_ore_poly_sigma_delta_t. sigma_delta_unable always returns GR_UNABLE; sigma_delta_commutative is the identity and zero; the derivative and Euler derivative versions differentiate a polynomial (with gr_poly_derivative, then a multiplication by x); the shift and difference versions compute Taylor shifts a(x \pm 1) (with gr_poly_taylor_shift) and their differences with a; sigma_delta_compose (used for q-shifts) composes a with the stored \sigma(x) = qx; sigma_delta_mahler substitutes x^b (an inflation); and sigma_delta_frobenius applies gr_fq_frobenius. All except the commutative and Frobenius versions require a base ring of univariate polynomials and return GR_UNABLE otherwise.

Negation, sum and difference, coefficientwise.

Add or subtract a constant c. The _other versions accept the same kinds of elements as gr_ore_poly_set_other, including an Ore polynomial with the same context.

Multiply by an integer or rational constant (which commutes with D), or multiply on the left by x, that is compute x L: an Ore polynomial with the same context is multiplied with gr_ore_poly_mul, and the other kinds of elements accepted by gr_ore_poly_set_other are constants c with c L = \sum_i (c a_i) D^i.

Set res to the left product D L = \sum_i (\sigma(a_i) D^{i+1} + \delta(a_i) D^i). The underscore version requires \mathit{len} \ge 1 and writes \mathit{len} + 1 coefficients.

Set res to the product L_1 L_2 in the Ore algebra, computed as \sum_i a_i (D^i L_2) with the powers D^i L_2 obtained by repeated left multiplication by D: O(\mathit{len1} \cdot \mathit{len2}) applications of \sigma and \delta and multiplications in the base ring. The underscore version requires positive lengths, writes \mathit{len1} + \mathit{len2} - 1 coefficients and does not allow aliasing.

Compute the right Euclidean division U = QV + R with \operatorname{ord} R < \operatorname{ord} V, which exists and is unique when the leading coefficient of V and its images under the powers of \sigma are invertible (over a field with \sigma injective, for instance). Each step divides the leading coefficient of the current remainder by \sigma^k(\operatorname{lc}(V)) and subtracts c D^k V, for k from \operatorname{ord} U - \operatorname{ord} V down to 0; the eliminated coefficients of R are then set to exact zeros (in inexact rings they would otherwise only be approximately zero). The non-underscore functions return GR_DOMAIN if V = 0; the underscore version requires \mathit{lenU} \ge \mathit{lenV} \ge 1 and writes \mathit{lenU} - \mathit{lenV} + 1 coefficients of Q and \mathit{lenU} of R. (In FLINT 3.6 and earlier the last step, k = 0, was skipped, so that for example D^2 + D + 1 divided by D gave Q = D and R = 1 + D.)