ore_algebra.guessing¶

Guessing tools

TESTS:

sage: from ore_algebra import OreAlgebra, guess
sage: guess([SR(1/(i+1)) for i in range(10)], OreAlgebra(QQ['n'], 'Sn'))
(-n - 2)*Sn + n + 1

Functions

`guess`(data, algebra, **kwargs)	Searches for an element of the algebra which annihilates the given data.
`guess_deq`(data, x, D, **kwargs)	Shortcut for `guess` applied with an Ore algebra of differential operators in D over K[x] where K is the parent of `data[0]`.
`guess_hp`(data, A[, order, degree, lift, …])	Guesses differential equations or algebraic equations for a given sample of terms.
`guess_mult`(data, algebra, **kwargs)	Searches for elements of the algebra which annihilates the given data.
`guess_mult_raw`(C, data, terms, points, …)	Low-level multivariate guessing function.
`guess_qrec`(data, qn, Q, q, **kwargs)	Shortcut for `guess` applied with an Ore algebra of q-recurrence operators in Q over K[qn] where K is the parent of q.
`guess_raw`(data, A[, order, degree, lift, …])	Guesses recurrence or differential equations for a given sample of terms.
`guess_rec`(data, n, S, **kwargs)	Shortcut for `guess` applied with an Ore algebra of shift operators in S over K[n] where K is the parent of `data[0]`.

ore_algebra.guessing.guess(data, algebra, **kwargs)¶

Searches for an element of the algebra which annihilates the given data.

INPUT:

data – a list of elements of the algebra’s base ring’s base ring K (or at least of objects which can be casted into this ring). If data is a string, it is assumed to be the name of a text file which contains the terms, one per line, encoded in a way that can be interpreted by the element constructor of K.
algebra – a univariate Ore algebra over a univariate polynomial ring whose generator is the standard derivation, the standard shift, the forward difference, a q-shift, or a commutative variable.

Optional arguments:

cut – if N is the minimum number of terms needed for some particular choice of order and degree, and if len(data) is more than N+cut, use data[:N+cut] instead of data. This must be a nonnegative integer or None. Default: None.
ensure – if N is the minimum number of terms needed for some particular choice of order and degree, and if len(data) is less than N+ensure, raise an error. This must be a nonnegative integer. Default: 0.
ncpus – number of processors to be used. Defaut: 1.
order – bounds the order of the operators being searched for. Default: infinity.
min_order – smallest order to be considered in the search. The output may nevertheless have lower order than this bound. Default: 1
degree – bounds the degree of the operators being searched for. The method may decide to overrule this setting if it thinks this may speed up the calculation. Default: infinity.
min_degree – smallest degree to be considered in the search. The output may nevertheless have lower degree than this bound. Default: 0
path – a list of pairs (r, d) specifying which orders and degrees the method should attempt. If this value is equal to None (default), a path is chosen which examines all the (r, d) which can be tested with the given amount of data.
solver – function to be used for computing the right kernel of a matrix with elements in K.
infolevel – an integer specifying the level of details of progress reports during the calculation.
method – either “linalg” (for linear algebra) or “hp” (for Hermite-Pade) or “automatic” (for the default choice), or a callable with the specification of a raw guesser.

OUTPUT:

An element of algebra which annihilates the given data.

An error is raised if no such element is found.

Note

This method is designed to find equations for D-finite objects. It may exhibit strange behaviour for objects which are holonomic but not D-finite.
When the generator of the algebra is a commutative variable, the method searches for algebraic equations.

EXAMPLES:

sage: from ore_algebra import *
sage: rec = guess([(2*i+1)^15 * (1 + 2^i + 3^i)^2 for i in range(1000)], OreAlgebra(ZZ['n'], 'Sn')) # long time (5 s)
sage: rec.order(), rec.degree() # long time
(6, 90)
sage: R.<t> = QQ['t']
sage: rec = guess([1/(i+t) + t^i for i in range(100)], OreAlgebra(R['n'], 'Sn'))
sage: rec
((-t + 1)*n^2 + (-2*t^2 - t + 2)*n - t^3 - 2*t^2)*Sn^2 + ((t^2 - 1)*n^2 + (2*t^3 + 3*t^2 - 2*t - 1)*n + t^4 + 3*t^3 + t^2 - t)*Sn + (-t^2 + t)*n^2 + (-2*t^3 + t)*n - t^4 - t^3 + t^2

sage: R.<C> = OreAlgebra(ZZ['x'])
sage: cat = [binomial(2*n,n) // (n+1) for n in range(10)]
sage: guess(cat, R)
-x*C^2 + C - 1

ore_algebra.guessing.guess_deq(data, x, D, **kwargs)¶

Shortcut for guess applied with an Ore algebra of differential operators in D over K[x] where K is the parent of data[0].

See the docstring of guess for further information.

ore_algebra.guessing.guess_hp(data, A, order=-1, degree=-1, lift=None, cut=25, ensure=0, infolevel=0)¶

Guesses differential equations or algebraic equations for a given sample of terms.

INPUT:

data – list of terms
A – an Ore algebra of differential operators or ordinary polynomials.
order – maximum order of the sought operators
degree – maximum degree of the sought operators
lift (optional) – a function to be applied to the terms in data prior to computation
cut (optional) – if N is the minimum number of terms needed for the the specified order and degree and len(data) is more than N+cut, use data[:N+cut] instead of data. This must be a nonnegative integer or None.
ensure (optional) – if N is the minimum number of terms needed for the specified order and degree and len(data) is less than N+ensure, raise an error. This must be a nonnegative integer.
infolevel (optional) – an integer indicating the desired amount of progress report to be printed during the calculation. Default: 0 (no output).

OUTPUT:

A basis of the K-vector space of all the operators L in A of order at most order and degree at most degree such that L applied to the truncated power series with data as terms gives the zero power series.

An error is raised in the following situations:

the algebra A has more than one generator, or its unique generator is neither a standard derivation nor a commutative variable.
data contains some item which does not belong to K, even after application of lift
if the condition on ensure is violated.

ALGORITHM:

Hermite-Pade approximation.

Note

This is a low-level method. Don’t call it directly unless you know what you are doing. In usual applications, the right method to call is guess.

EXAMPLES:

sage: from ore_algebra import *
sage: from ore_algebra.guessing import guess_hp
sage: K = GF(1091); R.<x> = K['x'];
sage: data = [binomial(2*n, n)*fibonacci(n)^3 for n in range(2000)]
sage: guess_hp(data, OreAlgebra(R, 'Dx'), order=4, degree=4, lift=K)
[(x^4 + 819*x^3 + 136*x^2 + 17*x + 635)*Dx^4 + (14*x^3 + 417*x^2 + 952*x + 605)*Dx^3 + (598*x^2 + 497*x + 99)*Dx^2 + (598*x + 794)*Dx + 893]
sage: len(guess_hp(data, OreAlgebra(R, 'C'), order=16, degree=64, lift=K))
1

ore_algebra.guessing.guess_mult(data, algebra, **kwargs)¶

Searches for elements of the algebra which annihilates the given data.

INPUT:

data – a nested list of elements of the algebra’s base ring’s base ring K (or at least of objects which can be casted into this ring). The depth of the nesting must match the number of generators of the algebra.
algebra – an Ore algebra over a polynomial ring all of whose generators are the standard derivation, the standard shift, or a q-shift.

Optional arguments:

cut – if N is the minimum number of terms needed for some particular choice of order and degree, and if len(data) is more than N+cut, use data[:N+cut] instead of data. This must be a nonnegative integer or None. Default: 100.
ensure – if N is the minimum number of terms needed for some particular choice of order and degree, and if len(data) is less than N+ensure, raise an error. This must be a nonnegative integer. Default: 0.
order – maximum degree of the algebra generators in the sought operators. Alternatively: a list or tuple specifying individual degree bounds for each generator of the algebra. Default: 2
degree – maximum total degree of the polynomial coefficients in the sought operators. Default: 3
point_filter – a callable such that index tuples of data array for which the callable returns ‘False’ will not be used. Default: None (everything allowed).
term_filter – a callable such that operators containing power products of the algebra generators for which the callable returns ‘False’ are excluded. Default: None (everything allowed).
solver – function to be used for computing the right kernel of a matrix with elements in K.
infolevel – an integer specifying the level of details of progress reports during the calculation.

OUTPUT:

The left ideal of algebra generated by all the operators of the specified order and degree that annihilate the given data. It may be the zero ideal.

Note

This method is designed to find equations for D-finite objects. It may exhibit strange behaviour for objects which are holonomic but not D-finite.

EXAMPLES:

sage: from ore_algebra import *
sage: from ore_algebra.guessing import guess_mult
sage: data = [[binomial(n,k) for n in range(10)] for k in range(10)]
sage: guess_mult(data, OreAlgebra(ZZ['n','k'], 'Sn', 'Sk'), order=1, degree=0)
Left Ideal (Sn*Sk - Sn - 1) of Multivariate Ore algebra in Sn, Sk over Fraction Field of Multivariate Polynomial Ring in n, k over Integer Ring
sage: guess_mult(data, OreAlgebra(ZZ['x','y'], 'Dx', 'Dy'), order=1, degree=1)
Left Ideal ((x + 1)*Dx + (-y)*Dy) of Multivariate Ore algebra in Dx, Dy over Fraction Field of Multivariate Polynomial Ring in x, y over Integer Ring
sage: guess_mult(data, OreAlgebra(ZZ['n','y'], 'Sn', 'Dy'), order=1, degree=1)
Left Ideal ((-y + 1)*Sn*Dy - Sn + (-y)*Dy - 1, (-n - 1)*Sn + y*Dy - n, (-y + 1)*Sn - y) of Multivariate Ore algebra in Sn, Dy over Fraction Field of Multivariate Polynomial Ring in n, y over Integer Ring
sage: guess_mult(data, OreAlgebra(ZZ['x','k'], 'Dx', 'Sk'), order=1, degree=1)
Left Ideal (Dx*Sk + (-x - 1)*Dx - 1, x*Dx*Sk + (x + 1)*Dx + (-k)*Sk - x, (x + 1)*Dx - k, (x + 1)*Dx*Sk + (-k - 1)*Sk) of Multivariate Ore algebra in Dx, Sk over Fraction Field of Multivariate Polynomial Ring in x, k over Integer Ring

ore_algebra.guessing.guess_mult_raw(C, data, terms, points, power, A, B, **kwargs)¶

Low-level multivariate guessing function. Do not call this method unless you know what you are doing. In most situations, you will want to call the function guess instead.

INPUT:

data – a nested list of elements of C
terms – a list of pairs of tuples (u, v) specifying exponent vectors u, v representing terms x^u D^v
points – a list of tuples specifying indices of the data array
power – a list of functions f mapping triples (n, u, v) of nonnegative integers to elements of C
A – a list of functions mapping triples (n, u, v) to integers
B – a list of functions mapping triples (n, u, v) to integers

OUTPUT:

A list of vectors generating the space of all vectors in C^len(terms) for which all(sum(prod(f[i][A[i][n[i],u[i],v[i]]]*a[B[i][n[i],u[i],v[i]]] for i in range(len(A))) for (u,v) in terms) == 0 for n in points)

SIDE EFFECT:

Elements of the list points which lead to a zero equation will be discarded.

ore_algebra.guessing.guess_qrec(data, qn, Q, q, **kwargs)¶

Shortcut for guess applied with an Ore algebra of q-recurrence operators in Q over K[qn] where K is the parent of q.

See the docstring of guess for further information.

ore_algebra.guessing.guess_raw(data, A, order=-1, degree=-1, lift=None, solver=None, cut=25, ensure=0, infolevel=0)¶

Guesses recurrence or differential equations for a given sample of terms.

INPUT:

data – list of terms
A – an Ore algebra of recurrence operators, differential operators, or q-differential operators.
order – maximum order of the sought operators
degree – maximum degree of the sought operators
lift (optional) – a function to be applied to the terms in data prior to computation
solver (optional) – a function to be used to compute the nullspace of a matrix with entries in the base ring of the base ring of A
cut (optional) – if N is the minimum number of terms needed for the the specified order and degree and len(data) is more than N+cut, use data[:N+cut] instead of data. This must be a nonnegative integer or None.
ensure (optional) – if N is the minimum number of terms needed for the specified order and degree and len(data) is less than N+ensure, raise an error. This must be a nonnegative integer.
infolevel (optional) – an integer indicating the desired amount of progress report to be printed during the calculation. Default: 0 (no output).

OUTPUT:

A basis of the K-vector space of all the operators L in A of order at most order and degree at most degree such that L applied to data gives an array of zeros. (resp. L applied to the truncated power series with data as terms gives the zero power series)

An error is raised in the following situations:

the algebra A has more than one generator, or its unique generator is neither a standard shift nor a q-shift nor a standard derivation.
data contains some item which does not belong to K, even after application of lift
if the condition on ensure is violated.
if the linear system constructed by the method turns out to be underdetermined for some other reason, e.g., because too many linear constraints happen to be trivial.

ALGORITHM:

Ansatz and linear algebra.

Note

This is a low-level method. Don’t call it directly unless you know what you are doing. In usual applications, the right method to call is guess.

EXAMPLES:

sage: from ore_algebra import *
sage: K = GF(1091); R.<n> = K['n']; A = OreAlgebra(R, 'Sn')
sage: data = [(5*n+3)/(3*n+4)*fibonacci(n)^3 for n in range(200)]
sage: guess_raw(data, A, order=5, degree=3, lift=K)
[(n^3 + 546*n^2 + 588*n + 786)*Sn^5 + (356*n^3 + 717*n^2 + 381*n + 449)*Sn^4 + (8*n^3 + 569*n^2 + 360*n + 214)*Sn^3 + (31*n^3 + 600*n^2 + 784*n + 287)*Sn^2 + (1078*n^3 + 1065*n^2 + 383*n + 466)*Sn + 359*n^3 + 173*n^2 + 503, (n^3 + 1013*n^2 + 593*n + 754)*Sn^5 + (797*n^3 + 56*n^2 + 7*n + 999)*Sn^4 + (867*n^3 + 1002*n^2 + 655*n + 506)*Sn^3 + (658*n^3 + 834*n^2 + 1036*n + 899)*Sn^2 + (219*n^3 + 479*n^2 + 476*n + 800)*Sn + 800*n^3 + 913*n^2 + 280*n]

ore_algebra.guessing.guess_rec(data, n, S, **kwargs)¶

Shortcut for guess applied with an Ore algebra of shift operators in S over K[n] where K is the parent of data[0].

See the docstring of guess for further information.

ore_algebra.guessing¶

Previous topic

Next topic