The MVPolyDict class

This class represents a mutivariate polynomial (typically sparse) with a Python dictionary; The keys represent the monomials of the polynomials (see the MVPolyDictMonomial class below) and the values, the non-zero coefficients.

The advantage of this sparse representation can be seen in the output of the following script which confirms the Euler four-square identity, discussed in 1749 in a letter from Euler to Goldbach

import time
from mvpoly.cube import *
from mvpoly.dict import *

for c in [MVPolyCube, MVPolyDict] :
    t0 = time.time()
    a1, a2, a3, a4, b1, b2, b3, b4 = c.variables(8)
    p = (a1**2 + a2**2 + a3**2 + a4**2) * (b1**2 + b2**2 + b3**2 + b4**2)
    q = (a1*b1 - a2*b2 - a3*b3 - a4*b4)**2 + \
        (a1*b2 + a2*b1 + a3*b4 - a4*b3)**2 + \
        (a1*b3 - a2*b4 + a3*b1 + a4*b2)**2 + \
        (a1*b4 + a2*b3 - a3*b2 + a4*b1)**2
    assert p == q, "failed Euler-Goldbach"
    t1 = time.time()
    print "%s %8.6f" % (c.__name__, t1 - t0)

which gives

MVPolyCube 0.254305
MVPolyDict 0.001889

indicating a speedup better than two orders of magnitude.

Method list

A list of all methods defined by the subclass. Naturally, the methods of the base class are also available.

class mvpoly.dict.MVPolyDict(arg=None, **kwargs)

Return an object of class MVPolyDict with the coefficient dictionary set to the optional coef argument.

__init__(arg=None, **kwargs)

__setitem__(index, value)

The setter method, which sets coefficient of the given index to the given value.

__getitem__(index)

The getter method, returning the coefficient of the specified index.

__add__(other)

Add an MVPolyDict to another, or to a number; return an MVPolyDict.

__radd__(other)

As add, but with the types in the opposite order – this is routed to add.

__neg__()

Negation of a polynomial, return the polynomial with negated coefficients.

__mul__(other)

Product of polynomials, or of a polynomial and a number.

__rmul__(other)

Reverse order multiply, as add

__eq__(other)

Equality of polynomials.

astype(dtype)

Return a polynomial using the specified dtype for the coefficients.

property coef

Return the dictionary of coefficients.

compose(*args)

Compose polynomials. The arguments, which should be MVPolyDict polynomials, are substituted into the corresponding variables of the polynomial.

property degrees

Return the maximal degrees of each of the variables of the polynomial as a tuple of integers

property degree

The (total, homogeneous) degree, the maximal sum of the monomial degrees of monomials with nonzero coefficients. Returns \(-1\) for the zero polynomial.

diff(*args)

Differentiate polynomial. The integer arguments should indicate the number to times to differentiate with respect to the corresponding polynomial variable, hence p.diff(0,1,1) would correspond to \(\partial^2 p / \partial y \partial z\).

eval(*args)

Evaluate the polynomial at the points given by args. There should be as many arguments as the polynomial has variables. The argument can be numbers, or arrays (all of the same shape).

int(*args, **kwargs)

Indefinite integral of polynomial. The arguments are as for diff().

property nonzero

Returns a list of 2-element tuples, for each the first being a (monomial) index, the second the corresponding coefficient. The indices do not have trailing zeros, so the return value for the polynomial \(p(x,y) = 2 + 3x + 4y\) would be [((), 2), ((1,), 3), ((0, 1), 4)].

classmethod init_from_nonzero(p, dtype)

Create a polynomial from one of any subclass; this is used internally by the __init__() constructor, but may be useful for direct application.

classmethod init_from_nonzero_tuples(d, dtype)

Create a polynomial from a list of tuples (in the format of poly.nonzero output).

classmethod variables(n, **kwargs)

Return a n-tuple of each of the variables (x, y, ..) of an n-variate system.

classmethod variable(i, _, **kwargs)

Return the i-th variable of an n-variate system, (i = 0, …, n-1).

classmethod monomials(n, k, **kwargs)

Return an array of all of the n-variate monomials of (homogeneous) degree less than or equal to k.

classmethod zero(**kwargs)

Return the zero polynomial.

classmethod one(**kwargs)

Return the unit (1) polynomial.

classmethod bell_partial(n, k, **kwargs)

The (n, k)-th partial Bell polynomial.

classmethod bell(n, **kwargs)

The n-th (complete) Bell polynomial.

classmethod bernstein(i, n, **kwargs)

Return the degree n Bernstein polynomial of the specified index i. Both n and i may be lists or tuples of non-negative numbers of the same size and with i dominated by n.

classmethod chsym(n, k, **kwargs)

Return the order k complete homogeneous symmetric polynomial in n variables.

__hash__ = None

Dictionary functions

Library code for the detailed work with the dictionaries is in the module mvpoly.utils.dict, it is not expected that these functions will be called directly.

mvpoly.util.dict.merge_dicts(d1, d2, merge)

Merges two dictionaries, non-destructively, combining values on duplicate keys as defined by the final merge argument.

This function is a modified version of an answer to a Stack Overflow question by rcreswick.

mvpoly.util.dict.merge_dicts_nonzero(d1, d2, merge)

As merge_dicts(), but not inserting into the results dictionary those item that would have a zero value.

mvpoly.util.dict.sum(d1, d2)

Return the sum of dictionaries with items with zero values removed.

mvpoly.util.dict.negate(d)

Return the dictionary that is its argument, but with the values negated.

Monomial class

The keys of the MVPolyDict dictionaries represent the monomials of the polynomial.

class mvpoly.dict.MVPolyDictMonomial(dict=None, key=None, index=None)

A class of sparse monomials, represented internally as a dict of variable numbers mapped to variable degrees (so that {0:2, 2:3} represents \(x^2 z^3\)). These can be serialised to a hashable key() or expressed in a dense index (the above monomial has length-4 index of (2, 0, 3, 0)).

__init__(dict=None, key=None, index=None)

__mul__(other)

Return the product of monomials.

property degree

The degree of the monomial: the sum of exponents.

property dict

The dictionary.

property index

The monomial as an tuple of variable exponents up to the last variable with nonzero exponent; thus m.index would return (3, 2) if m represents the monomial \(x^3 y^2\).

index_of_length(n)

Return the monomial as an n-tuple of variable exponents; thus m.index_of_length(3) would return (3, 2, 0) if m represents the monomial \(x^3y^2\).

property key

A hashable representation (as a tuple of pairs) of the dictionary.

property occurences

The monomial as a tuple of variable indices repeated as many times as the exponent of the variable; thus m.occurences would return (0, 0, 0, 1, 1) if m represents the monomial \(x^3 y^2\). The length of this vector is the degree of the monomial.