Source code for sympy.polys.monomialtools

"""Tools and arithmetics for monomials of distributed polynomials. """

from sympy.core.mul import Mul
from sympy.core.singleton import S
from sympy.core.basic import C

from sympy.polys.polyerrors import ExactQuotientFailed

from sympy.utilities import cythonized

from sympy.core.compatibility import cmp

[docs]def monomials(variables, degree): r""" Generate a set of monomials of the given total degree or less. Given a set of variables `V` and a total degree `N` generate a set of monomials of degree at most `N`. The total number of monomials is huge and is given by the following formula: .. math:: \frac{(\#V + N)!}{\#V! N!} For example if we would like to generate a dense polynomial of a total degree `N = 50` in 5 variables, assuming that exponents and all of coefficients are 32-bit long and stored in an array we would need almost 80 GiB of memory! Fortunately most polynomials, that we will encounter, are sparse. **Examples** Consider monomials in variables `x` and `y`:: >>> from sympy import monomials >>> from sympy.abc import x, y >>> sorted(monomials([x, y], 2)) [1, x, y, x**2, y**2, x*y] >>> sorted(monomials([x, y], 3)) [1, x, y, x**2, x**3, y**2, y**3, x*y, x*y**2, x**2*y] """ if not variables: return set([S.One]) else: x, tail = variables[0], variables[1:] monoms = monomials(tail, degree) for i in range(1, degree+1): monoms |= set([ x**i * m for m in monomials(tail, degree-i) ]) return monoms
[docs]def monomial_count(V, N): r""" Computes the number of monomials. The number of monomials is given by the following formula: .. math:: \frac{(\#V + N)!}{\#V! N!} where `N` is a total degree and `V` is a set of variables. **Examples** >>> from sympy import monomials, monomial_count >>> from sympy.abc import x, y >>> monomial_count(2, 2) 6 >>> M = monomials([x, y], 2) >>> sorted(M) [1, x, y, x**2, y**2, x*y] >>> len(M) 6 """ return C.factorial(V + N) / C.factorial(V) / C.factorial(N)
def monomial_lex_key(monom): """Key function for sorting monomials in lexicographic order. """ return monom def monomial_grlex_key(monom): """Key function for sorting monomials in graded lexicographic order. """ return (sum(monom), monom) def monomial_grevlex_key(monom): """Key function for sorting monomials in reversed graded lexicographic order. """ return (sum(monom), tuple(reversed(monom))) _monomial_key = { 'lex' : monomial_lex_key, 'grlex' : monomial_grlex_key, 'grevlex' : monomial_grevlex_key, } def monomial_key(order=None): """ Return a function defining admissible order on monomials. The result of a call to :func:`monomial_key` is a function which should be used as a key to :func:`sorted` built-in function, to provide order in a set of monomials of the same length. Currently supported monomial orderings are: 1. lex - lexicographic order (default) 2. grlex - graded lexicographic order 3. grevlex - reversed graded lexicographic order If the input argument is not a string but has ``__call__`` attribute, then it will pass through with an assumption that the callable object defines an admissible order on monomials. """ if order is None: return _monomial_key['lex'] if isinstance(order, str): try: return _monomial_key[order] except KeyError: raise ValueError("supported monomial orderings are 'lex', 'grlex' and 'grevlex', got %r" % order) elif hasattr(order, '__call__'): return order else: raise ValueError("monomial ordering specification must be a string or a callable, got %s" % order) def monomial_lex_cmp(a, b): return cmp(a, b) def monomial_grlex_cmp(a, b): return cmp(sum(a), sum(b)) or cmp(a, b) def monomial_grevlex_cmp(a, b): return cmp(sum(a), sum(b)) or cmp(tuple(reversed(b)), tuple(reversed(a))) _monomial_order = { 'lex' : monomial_lex_cmp, 'grlex' : monomial_grlex_cmp, 'grevlex' : monomial_grevlex_cmp, } def monomial_cmp(order): """ Returns a function defining admissible order on monomials. Currently supported orderings are: 1. lex - lexicographic order 2. grlex - graded lexicographic order 3. grevlex - reversed graded lexicographic order """ try: return _monomial_order[order] except KeyError: raise ValueError("expected valid monomial order, got %s" % order) @cythonized("a,b") def monomial_mul(A, B): """ Multiplication of tuples representing monomials. Lets multiply `x**3*y**4*z` with `x*y**2`:: >>> from sympy.polys.monomialtools import monomial_mul >>> monomial_mul((3, 4, 1), (1, 2, 0)) (4, 6, 1) which gives `x**4*y**5*z`. """ return tuple([ a + b for a, b in zip(A, B) ]) @cythonized("a,b,c") def monomial_div(A, B): """ Division of tuples representing monomials. Lets divide `x**3*y**4*z` by `x*y**2`:: >>> from sympy.polys.monomialtools import monomial_div >>> monomial_div((3, 4, 1), (1, 2, 0)) (2, 2, 1) which gives `x**2*y**2*z`. However:: >>> monomial_div((3, 4, 1), (1, 2, 2)) is None True `x*y**2*z**2` does not divide `x**3*y**4*z`. """ C = [ a - b for a, b in zip(A, B) ] if all([ c >= 0 for c in C ]): return tuple(C) else: return None @cythonized("a,b") def monomial_gcd(A, B): """ Greatest common divisor of tuples representing monomials. Lets compute GCD of `x**3*y**4*z` and `x*y**2`:: >>> from sympy.polys.monomialtools import monomial_gcd >>> monomial_gcd((3, 4, 1), (1, 2, 0)) (1, 2, 0) which gives `x*y**2`. """ return tuple([ min(a, b) for a, b in zip(A, B) ]) @cythonized("a,b") def monomial_lcm(A, B): """ Least common multiple of tuples representing monomials. Lets compute LCM of `x**3*y**4*z` and `x*y**2`:: >>> from sympy.polys.monomialtools import monomial_lcm >>> monomial_lcm((3, 4, 1), (1, 2, 0)) (3, 4, 1) which gives `x**3*y**4*z`. """ return tuple([ max(a, b) for a, b in zip(A, B) ]) @cythonized("i,n") def monomial_max(*monoms): """ Returns maximal degree for each variable in a set of monomials. Consider monomials `x**3*y**4*z**5`, `y**5*z` and `x**6*y**3*z**9`. We wish to find out what is the maximal degree for each of `x`, `y` and `z` variables:: >>> from sympy.polys.monomialtools import monomial_max >>> monomial_max((3,4,5), (0,5,1), (6,3,9)) (6, 5, 9) """ M = list(monoms[0]) for N in monoms[1:]: for i, n in enumerate(N): M[i] = max(M[i], n) return tuple(M) @cythonized("i,n") def monomial_min(*monoms): """ Returns minimal degree for each variable in a set of monomials. Consider monomials `x**3*y**4*z**5`, `y**5*z` and `x**6*y**3*z**9`. We wish to find out what is the minimal degree for each of `x`, `y` and `z` variables:: >>> from sympy.polys.monomialtools import monomial_min >>> monomial_min((3,4,5), (0,5,1), (6,3,9)) (0, 3, 1) """ M = list(monoms[0]) for N in monoms[1:]: for i, n in enumerate(N): M[i] = min(M[i], n) return tuple(M)
[docs]class Monomial(object): """Class representing a monomial, i.e. a product of powers. """ __slots__ = ['data'] def __init__(self, *data): self.data = tuple(map(int, data)) def __hash__(self): return hash((self.__class__.__name__, self.data)) def __repr__(self): return "Monomial(%s)" % ", ".join(map(str, self.data)) def as_expr(self, *gens): """Convert a monomial instance to a SymPy expression. """ return Mul(*[ gen**exp for gen, exp in zip(gens, self.data) ]) def __eq__(self, other): if isinstance(other, Monomial): return self.data == other.data else: return False def __ne__(self, other): return not self.__eq__(other) def __mul__(self, other): if isinstance(other, Monomial): return Monomial(*monomial_mul(self.data, other.data)) else: raise TypeError("an instance of Monomial class expected, got %s" % other) def __pow__(self, other): n = int(other) if not n: return Monomial(*((0,)*len(self.data))) elif n > 0: data = self.data for i in xrange(1, n): data = monomial_mul(data, self.data) return Monomial(*data) else: raise ValueError("a non-negative integer expected, got %s" % other) def __div__(self, other): if isinstance(other, Monomial): result = monomial_div(self.data, other.data) if result is not None: return Monomial(*result) else: raise ExactQuotientFailed(self, other) else: raise TypeError("an instance of Monomial class expected, got %s" % other) __floordiv__ = __truediv__ = __div__ def gcd(self, other): """Greatest common divisor of monomials. """ if isinstance(other, Monomial): return Monomial(*monomial_gcd(self.data, other.data)) else: raise TypeError("an instance of Monomial class expected, got %s" % other) def lcm(self, other): """Least common multiple of monomials. """ if isinstance(other, Monomial): return Monomial(*monomial_lcm(self.data, other.data)) else: raise TypeError("an instance of Monomial class expected, got %s" % other) @classmethod def max(cls, *monomials): """Returns maximal degree for each variable in a set of monomials. """ return Monomial(*monomial_max(*[ monomial.data for monomial in monomials ])) @classmethod def min(cls, *monomials): """Returns minimal degree for each variable in a set of monomials. """ return Monomial(*monomial_min(*[ monomial.data for monomial in monomials ]))