ore_algebra.ideal

Ideals

Functions

fglm(algebra, one_vector, gen_matrices[, …]) Constructs a Groebner basis using linear algebra.
solve_triangular_system(mat, rhs[, solver]) Constructs a vector space basis for the uncoupled system mat*f = rhs
uncouple(mat[, algebra, extended, …]) Triangularizes an operator matrix.

Classes

MonomialIterator(algebra) Iterate in increasing order over the monomials that are below some staircase that is determined in parallel to the iteration.
OreLeftIdeal(ring, gens[, coerce, …])
class ore_algebra.ideal.MonomialIterator(algebra)

Iterate in increasing order over the monomials that are below some staircase that is determined in parallel to the iteration. Tool for FGLM.

declare_step()

Informs this iterator that among the terms to be outputted in the future there should not be any multiples of the previously otuputted term.

next()

Returns (tau, D) such that tau*D is the next term in the iteration, D is an algebra generator, and tau is a term that was output earlier. The first output does not follow this rule but is (1, 1).

tau*D is the smallest term (in the term order) which has not been listed before and which is not a multiple of some term that has been declared as a step in the staircase

ore_algebra.ideal.fglm(algebra, one_vector, gen_matrices, infolevel=0, solver=None, early_termination=False)

Constructs a Groebner basis using linear algebra.

INPUT:

algebra – target algebra A = K(x,…)[X,…] one_vector – a vector in K(x,…)^n corresponding to the term 1 gen_matrices – a dictionary mapping the generators of A to nxn multiplication matrices infolevel – verbosity of progress reports solver – callable to be used to determine bases of right kernels of matrices over K(x,…) early_termination – if set to True, this returns only the first nonzero Groebner basis element encountered

OUTPUT:

The one_vector and the gen_matrices together with the sigma’s and delta’s of A turn K(x,…)^n into a left-A-module. The output of this function is the Groebner basis of the kernel of the natural homomorphism A –> K(x,…)^n.

EXAMPLES:

sage: from ore_algebra import *
sage: R.<n,k> = ZZ[]
sage: A.<Sn,Sk> = OreAlgebra(R)
sage: id1 = A.ideal([Sk-2*k,Sn-3])
sage: id2 = A.ideal([Sk-3,Sn-n])
sage: id1.intersection(id2)
Left Ideal ((-2*k + 3)*Sn + (-n + 3)*Sk + 2*n*k - 9, (-2*k + 3)*Sk^2 + (4*k^2 + 4*k - 9)*Sk - 12*k^2 + 6*k) of Multivariate Ore algebra in Sn, Sk over Fraction Field of Multivariate Polynomial Ring in n, k over Integer Ring
sage: _.intersection(_)
Left Ideal ((-2*k + 3)*Sn + (-n + 3)*Sk + 2*n*k - 9, (-2*k + 3)*Sk^2 + (4*k^2 + 4*k - 9)*Sk - 12*k^2 + 6*k) of Multivariate Ore algebra in Sn, Sk over Fraction Field of Multivariate Polynomial Ring in n, k over Integer Ring

sage: R.<x, y> = ZZ[]
sage: A.<Dx,Dy> = OreAlgebra(R)
sage: id1 = A.ideal([2*Dx-Dy, (x+2*y)*Dy^2 + Dy])
sage: id2 = A.ideal([Dy - x, Dx - y])
sage: id1.intersection(id2)
Left Ideal ((-x^2 + 4*y^2)*Dy^2 + (-2*x^3 - 4*x^2*y - 2*x)*Dx + (x^3 + 2*x^2*y + 2*y)*Dy, (-x^2 + 4*y^2)*Dx*Dy + (-2*x^2*y - 4*x*y^2 - 3*x - 4*y)*Dx + (x^2*y + 2*x*y^2 + x + 3*y)*Dy, (-2*x^2 + 8*y^2)*Dx^2 + (-4*x*y^2 - 8*y^3 - x)*Dx + (2*x*y^2 + 4*y^3 + y)*Dy) of Multivariate Ore algebra in Dx, Dy over Fraction Field of Multivariate Polynomial Ring in x, y over Integer Ring
sage: _.intersection(_)
Left Ideal ((-x^2 + 4*y^2)*Dy^2 + (-2*x^3 - 4*x^2*y - 2*x)*Dx + (x^3 + 2*x^2*y + 2*y)*Dy, (-x^2 + 4*y^2)*Dx*Dy + (-2*x^2*y - 4*x*y^2 - 3*x - 4*y)*Dx + (x^2*y + 2*x*y^2 + x + 3*y)*Dy, (-2*x^2 + 8*y^2)*Dx^2 + (-4*x*y^2 - 8*y^3 - x)*Dx + (2*x*y^2 + 4*y^3 + y)*Dy) of Multivariate Ore algebra in Dx, Dy over Fraction Field of Multivariate Polynomial Ring in x, y over Integer Ring
ore_algebra.ideal.solve_triangular_system(mat, rhs, solver=None)

Constructs a vector space basis for the uncoupled system mat*f = rhs

INPUT:

mat – an upper triangular matrix of univariate operators, given as a list of list. rhs – a vector of right hand sides.

OUTPUT:

a list of pairs (u, c) where u is a list of rational functions and c is a list of constants such that mat*u == c*rhs and every other pair (u, c) with mat*u == c*rhs is a linear combination (with constant coefficients) of the pairs in the output

EXAMPLES:

sage: from ore_algebra import *
sage: from ore_algebra.ideal import solve_triangular_system
sage: R.<x> = ZZ[]; A.<Dx> = OreAlgebra(R); 
sage: solve_triangular_system([list(map(A, [Dx-x, 2,x])), list(map(A, [0,x,Dx-4])), list(map(A, [0,0,Dx]))], [[1,0,0],[0,1,0],[0,0,1]])
[([1, 0, 1], [0, -4, 0]), ([x, 4, x], [9, 1, 1])]
ore_algebra.ideal.uncouple(mat, algebra=None, extended=False, column_swaps=False, infolevel=0)

Triangularizes an operator matrix.

The matrix is to be specified as lists of lists. The inner lists represent the rows of the matrix. The output matrix will be in staircase form. Row operations applied during the transformation act on the matrix from the left.

EXAMPLES:

sage: from ore_algebra import *
sage: from ore_algebra.ideal import uncouple
sage: R.<x> = ZZ[]
sage: A.<Dx> = OreAlgebra(R)
sage: uncouple([[Dx, 3*Dx - 1], [x-Dx, x]])
[[x, 3*Dx + x - 1], [0, -3*x*Dx^2 + (2*x^2 + x + 3)*Dx - x^2 - 1]]
sage: uncouple([[Dx-x, 2,x], [3, x, Dx-4], [x*Dx-4, 4-x, 4]])
[[3, x, Dx - 4],
 [0, x^3 + 5*x - 12, (x^2 - 4)*Dx - x^2 + 4],
 [0,
  0,
  (-3*x^4 + 4*x^3 - 15*x^2 + 56*x - 48)*Dx^2 + (x^6 + x^5 + 9*x^4 - 9*x^3 - 4*x^2 - 88*x + 112)*Dx - x^5 + 4*x^4 - 19*x^3 + 44*x^2 - 88*x + 80]]