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_compose, used for $q$-shifts, composes $a$ with the stored $\sigma(x)$).

Set res to the result of applying P to the base ring element f. The first function uses the standard interpretation of P as an operator acting on the base ring (derivative operators differentiate, shift operators shift, etc.). In the second one, the generator $D$ acts by $g \mapsto \sigma(g) \, d_1 + \delta(g)$ where d1 is the value $D(1)$; any d1 defines a valid action.

Rewrite op, of length len, from ORE_ALGEBRA_EULER_DERIVATIVE to ORE_ALGEBRA_DERIVATIVE (first function), or from ORE_ALGEBRA_DERIVATIVE to ORE_ALGEBRA_EULER_DERIVATIVE (second function). In the latter case the result is multiplied by a power of $x$: $\mathit{res} = x^{\mathit{len}-1} \cdot \mathit{op}$. Here ctx is the common base ring and var is the index of the generator $x$ of ctx on which the derivations act. The output vector res has the same length len as op and must not alias it.

Rewrite op from src_alg to dst_alg, where both are among the builtin shift and difference algebras (corresponding to operators written in terms of the forward and backward shifts $S$, $S^{-1}$ and the forward and backward differences $S - 1$, $1 - S^{-1}$). The result satisfies $S^p \cdot \mathit{res} = \mathit{op}$. Here ctx is the common base ring and var is the index of the generator of ctx on which $S$ acts. Conversions that cross between the forward side ($S$, $S - 1$) and the backward side ($S^{-1}$, $1 - S^{-1}$) currently require a generic univariate polynomial base ring and otherwise return GR_UNABLE. The function returns an error status when the source or destination algebra is not of the required type. The output vector res has the same length len as op and must not alias it.

The second function is the specialisation to conversions between ORE_ALGEBRA_FORWARD_DIFFERENCE and ORE_ALGEBRA_BACKWARD_DIFFERENCE, the flag to_backward giving the direction.

Convert op from op_ctx to res_ctx. The meaning of the output parameter p depends on the algebra. For a conversion within the differential family, $x^p \cdot \mathit{res} = \mathit{op}$ where $x$ is the generator of the base ring specified in the source context. For a conversion within the shift/difference family, $S^p \cdot \mathit{res} = \mathit{op}$ (a power of the forward shift $S$). No attempt is currently made to minimise $p$ or its absolute value.

The two inverse rewritings of the isomorphism between the Euler operator and the backward shift $S^{-1}$. The common base ring ctx must be a univariate polynomial ring. The caller allocates res to reslen, one more than the largest coefficient degree of op.

Given a differential operator op represented as an element of op_ctx, compute a shift/difference operator res in res_ctx and an integer p such that the above correspondence maps op to $S^p \cdot \mathit{res}$ (first function); or, conversely, given a shift/difference operator op, compute a differential operator res and p such that the correspondence maps op to $x^p \cdot \mathit{res}$ (second function). The generators of the base rings specified in the source and destination contexts play the role of $x$ and $n$ (first function), or $n$ and $x$ (second function). No attempt is currently made to minimise $p$ or its absolute value.

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$.)