This module provides support for holonomic sequences and functions, which are represented via annihilating operators \(A = \sum_{i=0}^r a_i D^i\) where \(a_i \in \mathbb{Z}[x]\).
Depending on context, \(D\) is one of the following:
A forward shift operator \(D f(x) = f(x+1)\), making \(A\) a difference operator which defines a family of sequences \(c(x)\) satisfying the difference equation
A differential operator \(D f(x) = f'(x)\), making \(A\) a differential operator which defines a family of functions \(f(x)\) satisfying the differential equation
A specific sequence of function is defined by fixing \(r\) initial values (derivatives), where \(r\) is called the order of the operator \(A\).
Represents a holonomic difference or differential operator as a sequence of coefficients of type fmpz_poly_struct.
An fmpz_holonomic_t is defined as an array of length one of type fmpz_holonomic_t, permitting an fmpz_holonomic_t to be passed by reference.
Initializes op for use, setting it to the zero operator (note that this is not a valid operator for input to most functions).
Clears op, deallocating all coefficients and the coefficient array.
Makes sure that the coefficient array of the operator contains at least len initialized polynomials.
Directly changes the length of the operator, without allocating or deallocating coefficients. The value shold not exceed the allocation length.
Sets \(op\) to a copy of \(op\).
Sets op to the constant operator 1. As a differential operator, this annihilates the zero function. As a difference operator, it annihilates the zero sequence.
Sets op to a random nonzero operator of order at most r, degree at most d, and with coefficients at most b bits in size. The operator is guaranteed to have a nonzero leading coefficient, but otherwise will not be normalised.
Returns the order r of op.
Returns the degree d of op, defined as the highest degree of all its coefficients.
Returns nonzero if op is zero-order, i.e. annihilates constant sequences.
Returns nonzero if op has constant coefficients, i.e. annihilates C-finite sequences.
Return nonzero if op is first-order, i.e. annihilates hypergeometric sequences.
Prints a pretty representation of op, using the string x for the variable of the coefficient polynomials, and using the string d for the differential or difference operator.
Normalises op by removing leading zero coefficients.
Normalises op by making the leading coefficient of the leading polynomial positive.
Normalises op by dividing out the content, i.e. the greatest common divisor, of all the coefficients.
Normalises op as a difference operator by removing trailing zero coefficients. This requires shifting the higher-order coefficients to compensate.
Normalises op as a difference operator by removing leading and trailing zero coefficients, removing the content, and making the leading polynomial positive.
Given an operator op annihilating a function or sequence \(f(x)\), sets res to an annihilator of the shifted function or sequence \(f(x+s)\).
Sets op to an annihilator of the constant sequence \(c, c, c, \ldots\) where \(c\) is arbitrary.
Sets op to an annihilator of the sequence \(c, c^2, c^3, \ldots\).
Sets op to an annihilator of the sequence of factorials \(n!\).
Sets op to an annihilator of the sequence of harmonic numbers \(H_n = 1 + 1/2 + 1/3 + \ldots + 1/n\).
Sets op to an annihilator of the sequence of Fibonacci numbers \(F_n\).
Sets op to a differential operator annihilating the power function \(x^c\).
Sets op to a differential operator annihilating the exponential function \(e^x\).
Sets op to a differential operator annihilating the sine and cosine functions \(\sin(x)\) and \(\cos(x)\).
Sets op to a differential operator annihilating the natural logarithm \(\log(x)\).
Sets op to a differential operator annihilating the inverse tangent function \(\operatorname{atan}(x)\).
Sets op to a differential operator annihilating the inverse sine and cosine functions \(\operatorname{asin}(x)\) and \(\operatorname{acos}(x)\).
Sets op to a differential operator annihilating the error function \(\operatorname{erf}(x)\).
Given annihilators op1 and op2 of sequences \(a_0, a_1, \ldots\) and \(b_0, b_1, \ldots\), sets res to an annihilator of the sequence \(a_0 b_0, a_1 b_1, \ldots\). This function currently requires op1 and op2 to be hypergeometric (i.e. of order 1).
Given an annihilator op of the sequence \(c_0, c_1, c_2, \ldots\), outputs an annihilator of the sequence \(c_0^e, c_1^e, c_2^e, \ldots\). This function currently requires op to be hypergeometric (i.e. of order 1).
Given an annihilator op of the sequence \(c(n)\), sets res to an annihilator of the sequence \(c(-n)\).
Given an annihilator op of the sequence \(c(n)\) and an integer constant m, sets res to an annihilator of the sequence \(c(mn)\). The constant m can be zero or negative.
Given a differential operator de annihilating some function \(f(x)\), sets re to a difference operator annihilating the coefficients \(c_k\) in the Taylor series at \(x = 0\),
Let op be an operator of order r annihilating a sequence \(c(k)\). This function computes an r by r integer matrix \(M\) and a denominator \(Q\) such that, for any initial values \(c(s), c(s+1), \ldots, c(s+r-1)\) where \(s\) is given by start,
The output is computed by multiplying together successive companion matrices, using binary splitting to balance the sizes of the subproducts.
Some special cases are handled more efficiently. In particular, if op has constant coefficients, matrix exponentiation is used.
In general, no attempt is made to divide out content from \(M\) and \(Q\). If \(Q\) is zero, the leading coefficient of op has a root somewhere among the evaluation points, making the sequence undefined from that point onward.
It is assumed that start + n does not overflow a long (to start from a larger initial value, one can shift the operator).
Equivalent to the fmpz_mat version, but truncates large entries.
Computes a forward matrix modulo the word-size modulus of M. This function implements a sublinear algorithm: letting \(m = \lfloor \sqrt n \rfloor\), we multiply together \(m\) shifted companion matrices, evaluate them at the points \(0, m, 2m, \ldots, m(m-1)\) using fast multipoint evaluation, and finally multiply together the evaluated matrices. This implementation is not intended to be optimal for small n.
Computes element \(c(n)\) in the sequence annihilated by the difference operator op, given the initial values \(c(n_0), c(n_1), \ldots, c(n_0+r-1)\) where \(r\) is the order of op. This is done by computing a forward matrix, and is not optimal for small n. The fmpz version assumes that the result is actually an integer.