PolyDict engine for generic multivariate polynomial rings

This module provides an implementation of the underlying arithmetic for multi-variate polynomial rings using Python dicts.

This class is not meant for end users, but instead for implementing multivariate polynomial rings over a completely general base. It does not do strong type checking or have parents, etc. For speed, it has been implemented in Cython.

The functions in this file use the ‘dictionary representation’ of multivariate polynomials

{(e1,...,er):c1,...} <-> c1*x1^e1*...*xr^er+...,

which we call a polydict. The exponent tuple (e1,...,er) in this representation is an instance of the class ETuple. This class behaves like a normal Python tuple but also offers advanced access methods for sparse monomials like positions of non-zero exponents etc.

AUTHORS:

• William Stein
• David Joyner
• Martin Albrecht (ETuple)
• Joel B. Mohler (2008-03-17) – ETuple rewrite as sparse C array

class sage.rings.polynomial.polydict.ETuple

Bases: object

Representation of the exponents of a polydict monomial. If (0,0,3,0,5) is the exponent tuple of x_2^3*x_4^5 then this class only stores {2:3, 4:5} instead of the full tuple. This sparse information may be obtained by provided methods.

The index/value data is all stored in the _data C int array member variable. For the example above, the C array would contain 2,3,4,5. The indices are interlaced with the values.

This data structure is very nice to work with for some functions implemented in this class, but tricky for others. One reason that I really like the format is that it requires a single memory allocation for all of the values. A hash table would require more allocations and presumably be slower. I didn’t benchmark this question (although, there is no question that this is much faster than the prior use of python dicts).

combine_to_positives(other)

Given a pair of ETuples (self, other), returns a triple of ETuples (a, b, c) so that self = a + b, other = a + c and b and c have all positive entries.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([-2,1,-5, 3, 1,0])
sage: f = ETuple([1,-3,-3,4,0,2])
sage: e.combine_to_positives(f)
((-2, -3, -5, 3, 0, 0), (0, 4, 0, 0, 1, 0), (3, 0, 2, 1, 0, 2))

common_nonzero_positions(other, sort=False)

Returns an optionally sorted list of non zero positions either in self or other, i.e. the only positions that need to be considered for any vector operation.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: f = ETuple([0,0,1])
sage: e.common_nonzero_positions(f)
{0, 2}
sage: e.common_nonzero_positions(f, sort=True)
[0, 2]

dotprod(other)

Return the dot product of this tuple by other.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: f = ETuple([0,1,1])
sage: e.dotprod(f)
2
sage: e = ETuple([1,1,-1])
sage: f = ETuple([0,-2,1])
sage: e.dotprod(f)
-3

eadd(other)

Vector addition of self with other.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: f = ETuple([0,1,1])
sage: e.eadd(f)
(1, 1, 3)

Verify that trac ticket #6428 has been addressed:

sage: R.<y, z> = Frac(QQ['x'])[]
sage: type(y)
<class 'sage.rings.polynomial.multi_polynomial_element.MPolynomial_polydict'>
sage: y^(2^32)
Traceback (most recent call last):
...
OverflowError: exponent overflow (2147483648)

eadd_p(other, pos)

Add other to self at position pos.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: e.eadd_p(5, 1)
(1, 5, 2)
sage: e = ETuple([0]*7)
sage: e.eadd_p(5,4)
(0, 0, 0, 0, 5, 0, 0)

sage: ETuple([0,1]).eadd_p(1, 0) == ETuple([1,1])
True

emax(other)

Vector of maximum of components of self and other.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: f = ETuple([0,1,1])
sage: e.emax(f)
(1, 1, 2)
sage: e = ETuple((1,2,3,4))
sage: f = ETuple((4,0,2,1))
sage: f.emax(e)
(4, 2, 3, 4)
sage: e = ETuple((1,-2,-2,4))
sage: f = ETuple((4,0,0,0))
sage: f.emax(e)
(4, 0, 0, 4)
sage: f.emax(e).nonzero_positions()
[0, 3]

emin(other)

Vector of minimum of components of self and other.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: f = ETuple([0,1,1])
sage: e.emin(f)
(0, 0, 1)
sage: e = ETuple([1,0,-1])
sage: f = ETuple([0,-2,1])
sage: e.emin(f)
(0, -2, -1)

emul(factor)

Scalar Vector multiplication of self.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: e.emul(2)
(2, 0, 4)

escalar_div(n)

Divide each exponent by n.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: ETuple([1,0,2]).escalar_div(2)
(0, 0, 1)
sage: ETuple([0,3,12]).escalar_div(3)
(0, 1, 4)

sage: ETuple([1,5,2]).escalar_div(0)
Traceback (most recent call last):
...
ZeroDivisionError

esub(other)

Vector subtraction of self with other.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: f = ETuple([0,1,1])
sage: e.esub(f)
(1, -1, 1)

is_constant()

Return if all exponents are zero in the tuple.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: e.is_constant()
False
sage: e = ETuple([0,0])
sage: e.is_constant()
True

is_multiple_of(n)

Test whether each entry is a multiple of n.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple

sage: ETuple([0,0]).is_multiple_of(3)
True
sage: ETuple([0,3,12,0,6]).is_multiple_of(3)
True
sage: ETuple([0,0,2]).is_multiple_of(3)
False

nonzero_positions(sort=False)

Return the positions of non-zero exponents in the tuple.

INPUT:

• sort – (default: False) if True a sorted list is returned; if False an unsorted list is returned

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2])
sage: e.nonzero_positions()
[0, 2]

nonzero_values(sort=True)

Return the non-zero values of the tuple.

INPUT:

• sort – (default: True) if True the values are sorted by their indices; otherwise the values are returned unsorted

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([2,0,1])
sage: e.nonzero_values()
[2, 1]
sage: f = ETuple([0,-1,1])
sage: f.nonzero_values(sort=True)
[-1, 1]

reversed()

Return the reversed ETuple of self.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,2,3])
sage: e.reversed()
(3, 2, 1)

sparse_iter()

Iterator over the elements of self where the elements are returned as (i, e) where i is the position of e in the tuple.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,0,2,0,3])
sage: list(e.sparse_iter())
[(0, 1), (2, 2), (4, 3)]

unweighted_degree()

Return the sum of entries.

ASSUMPTION:

All entries are non-negative.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple
sage: e = ETuple([1,1,0,2,0])
sage: e.unweighted_degree()
4

class sage.rings.polynomial.polydict.PolyDict

Bases: object

INPUT:

• pdict – dict or list, which represents a multi-variable polynomial with the distribute representation (a copy is not made)
• zero – (optional) zero in the base ring
• force_int_exponents – bool (optional) arithmetic with int exponents is much faster than some of the alternatives, so this is True by default.
• force_etuples – bool (optional) enforce that the exponent tuples are instances of ETuple class

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: PolyDict({(2,3):2, (1,2):3, (2,1):4})
PolyDict with representation {(1, 2): 3, (2, 1): 4, (2, 3): 2}

# I've removed fractional exponent support in ETuple when moving to a sparse C integer array
#sage: PolyDict({(2/3,3,5):2, (1,2,1):3, (2,1):4}, force_int_exponents=False)
#PolyDict with representation {(2, 1): 4, (1, 2, 1): 3, (2/3, 3, 5): 2}

sage: PolyDict({(2,3):0, (1,2):3, (2,1):4}, remove_zero=True)
PolyDict with representation {(1, 2): 3, (2, 1): 4}

sage: PolyDict({(0,0):RIF(-1,1)}, remove_zero=True)
PolyDict with representation {(0, 0): 0.?}

coefficient(mon)

Return a polydict that defines a polynomial in 1 less number of variables that gives the coefficient of mon in this polynomial.

The coefficient is defined as follows. If f is this polynomial, then the coefficient is the sum T/mon where the sum is over terms T in f that are exactly divisible by mon.

coefficients()

Return the coefficients of self.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: sorted(f.coefficients())
[2, 3, 4]

degree(x=None)

dict()

Return a copy of the dict that defines self. It is safe to change this. For a reference, use dictref.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.dict()
{(1, 2): 3, (2, 1): 4, (2, 3): 2}

exponents()

Return the exponents of self.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: sorted(f.exponents())
[(1, 2), (2, 1), (2, 3)]

homogenize(var)

is_homogeneous()

latex(vars, atomic_exponents=True, atomic_coefficients=True, sortkey=None)

Return a nice polynomial latex representation of this PolyDict, where the vars are substituted in.

INPUT:

• vars – list
• atomic_exponents – bool (default: True)
• atomic_coefficients – bool (default: True)

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.latex(['a', 'WW'])
'2 a^{2} WW^{3} + 4 a^{2} WW + 3 a WW^{2}'

When atomic_exponents is False, the exponents are surrounded in parenthesis, since ^ has such high precedence:

# I've removed fractional exponent support in ETuple when moving to a sparse C integer array
#sage: f = PolyDict({(2/3,3,5):2, (1,2,1):3, (2,1,1):4}, force_int_exponents=False)
#sage: f.latex(['a', 'b', 'c'], atomic_exponents=False)
#'4 a^{2}bc + 3 ab^{2}c + 2 a^{2/3}b^{3}c^{5}'

lcmt(greater_etuple)

Provides functionality of lc, lm, and lt by calling the tuple compare function on the provided term order T.

INPUT:

• greater_etuple – a term order

list()

Return a list that defines self. It is safe to change this.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: sorted(f.list())
[[2, [2, 3]], [3, [1, 2]], [4, [2, 1]]]

max_exp()

Returns an ETuple containing the maximum exponents appearing. If there are no terms at all in the PolyDict, it returns None.

The nvars parameter is necessary because a PolyDict doesn’t know it from the data it has (and an empty PolyDict offers no clues).

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.max_exp()
(2, 3)
sage: PolyDict({}).max_exp() # returns None

min_exp()

Returns an ETuple containing the minimum exponents appearing. If there are no terms at all in the PolyDict, it returns None.

The nvars parameter is necessary because a PolyDict doesn’t know it from the data it has (and an empty PolyDict offers no clues).

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.min_exp()
(1, 1)
sage: PolyDict({}).min_exp() # returns None

monomial_coefficient(mon)

INPUT:

a PolyDict with a single key

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.monomial_coefficient(PolyDict({(2,1):1}).dict())
4

poly_repr(vars, atomic_exponents=True, atomic_coefficients=True, sortkey=None)

Return a nice polynomial string representation of this PolyDict, where the vars are substituted in.

INPUT:

• vars – list
• atomic_exponents – bool (default: True)
• atomic_coefficients – bool (default: True)

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.poly_repr(['a', 'WW'])
'2*a^2*WW^3 + 4*a^2*WW + 3*a*WW^2'

When atomic_exponents is False, the exponents are surrounded in parenthesis, since ^ has such high precedence.

# I've removed fractional exponent support in ETuple when moving to a sparse C integer array
#sage: f = PolyDict({(2/3,3,5):2, (1,2,1):3, (2,1,1):4}, force_int_exponents=False)
#sage: f.poly_repr(['a', 'b', 'c'], atomic_exponents=False)
#'4*a^(2)*b*c + 3*a*b^(2)*c + 2*a^(2/3)*b^(3)*c^(5)'

We check to make sure that when we are in characteristic two, we don’t put negative signs on the generators.

sage: Integers(2)['x, y'].gens()
(x, y)

We make sure that intervals are correctly represented.

sage: f = PolyDict({(2,3):RIF(1/2,3/2), (1,2):RIF(-1,1)})
sage: f.poly_repr(['x', 'y'])
'1.?*x^2*y^3 + 0.?*x*y^2'

polynomial_coefficient(degrees)

Return a polydict that defines the coefficient in the current polynomial viewed as a tower of polynomial extensions.

INPUT:

• degrees – a list of degree restrictions; list elements are None if the variable in that position should be unrestricted

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.polynomial_coefficient([2,None])
PolyDict with representation {(0, 1): 4, (0, 3): 2}
sage: f = PolyDict({(0,3):2, (0,2):3, (2,1):4})
sage: f.polynomial_coefficient([0,None])
PolyDict with representation {(0, 2): 3, (0, 3): 2}

rich_compare(other, op, sortkey=None)

Compare two \(PolyDict\) argument is given it should be a sort key used to specify a term order.

If not sort key is provided than only comparison by equality (== or !=) is supported.

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: from sage.structure.richcmp import op_EQ, op_NE, op_LT
sage: p1 = PolyDict({(0,): 1})
sage: p2 = PolyDict({(0,): 2})
sage: p1.rich_compare(PolyDict({(0,): 1}), op_EQ)
True
sage: p1.rich_compare(p2, op_EQ)
False
sage: p1.rich_compare(p2, op_NE)
True
sage: p1.rich_compare(p2, op_LT)
Traceback (most recent call last):
...
TypeError: ordering of PolyDicts requires a sortkey

sage: O = TermOrder()
sage: p1.rich_compare(p2, op_LT, O.sortkey)
True

sage: p3 = PolyDict({(3, 2, 4): 1, (3, 2, 5): 2})
sage: p4 = PolyDict({(3, 2, 4): 1, (3, 2, 3): 2})
sage: p3.rich_compare(p4, op_LT, O.sortkey)
False

scalar_lmult(s)

Left Scalar Multiplication

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: x, y = FreeMonoid(2, 'x, y').gens()  # a strange object to live in a polydict, but non-commutative!
sage: f = PolyDict({(2,3):x})
sage: f.scalar_lmult(y)
PolyDict with representation {(2, 3): y*x}
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.scalar_lmult(-2)
PolyDict with representation {(1, 2): -6, (2, 1): -8, (2, 3): -4}
sage: f.scalar_lmult(RIF(-1,1))
PolyDict with representation {(1, 2): 0.?e1, (2, 1): 0.?e1, (2, 3): 0.?e1}

scalar_rmult(s)

Right Scalar Multiplication

EXAMPLES:

sage: from sage.rings.polynomial.polydict import PolyDict
sage: x, y = FreeMonoid(2, 'x, y').gens()  # a strange object to live in a polydict, but non-commutative!
sage: f = PolyDict({(2,3):x})
sage: f.scalar_rmult(y)
PolyDict with representation {(2, 3): x*y}
sage: f = PolyDict({(2,3):2, (1,2):3, (2,1):4})
sage: f.scalar_rmult(-2)
PolyDict with representation {(1, 2): -6, (2, 1): -8, (2, 3): -4}
sage: f.scalar_rmult(RIF(-1,1))
PolyDict with representation {(1, 2): 0.?e1, (2, 1): 0.?e1, (2, 3): 0.?e1}

term_lmult(exponent, s)

Return this element multiplied by s on the left and with exponents shifted by exponent.

INPUT:

• exponent – a ETuple
• s – a scalar

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple, PolyDict
sage: x, y = FreeMonoid(2, 'x, y').gens()  # a strange object to live in a polydict, but non-commutative!
sage: f = PolyDict({(2, 3): x})
sage: f.term_lmult(ETuple((1, 2)), y)
PolyDict with representation {(3, 5): y*x}

sage: f = PolyDict({(2,3): 2, (1,2): 3, (2,1): 4})
sage: f.term_lmult(ETuple((1, 2)), -2)
PolyDict with representation {(2, 4): -6, (3, 3): -8, (3, 5): -4}

term_rmult(exponent, s)

Return this element multiplied by s on the right and with exponents shifted by exponent.

INPUT:

• exponent – a ETuple
• s – a scalar

EXAMPLES:

sage: from sage.rings.polynomial.polydict import ETuple, PolyDict
sage: x, y = FreeMonoid(2, 'x, y').gens()  # a strange object to live in a polydict, but non-commutative!
sage: f = PolyDict({(2, 3): x})
sage: f.term_rmult(ETuple((1, 2)), y)
PolyDict with representation {(3, 5): x*y}

sage: f = PolyDict({(2,3): 2, (1,2): 3, (2,1): 4})
sage: f.term_rmult(ETuple((1, 2)), -2)
PolyDict with representation {(2, 4): -6, (3, 3): -8, (3, 5): -4}

total_degree()

valuation(x=None)

sage.rings.polynomial.polydict.make_ETuple(data, length)

sage.rings.polynomial.polydict.make_PolyDict(data)