polynomial.py

from pymwp import Polynomial

Polynomial

Polynomial(*monomials: Optional[Union[str, Monomial, Tuple[str, DELTAS]]])

A polynomial is an ordered list of ordered Monomials.

For polynomials, I introduce a total order on the monomials. This eases the computation of the sum: if we want to add a monomial to an ordered list of monomials, we compare the monomial to each of the elements of the list until we find either an element which is equal (and then we sum the scalars) or an element which is larger (and then we insert the new monomial there).

Polynomials use the following ordering: \(\delta(i,j)\) is smaller than \(\delta(m,n)\) iff either \(j<n\) or \((j==n)\) and \((i<m)\).

This is extended to products (which we consider ordered!) by letting \(\prod_k\delta(i_k,j_k) < \prod_l\delta(m_l,n_l)\) iff \(\delta(i_1,j_1) < \delta(m_1,n_1)\).

Attributes:

Name	Type	Description
list	List[Monomial]	List of monomials.

Create a polynomial.

Example

Create polynomial with 0-monomial:

zero = Polynomial()

Create polynomial with one monomial with specific scalar:

poly = Polynomial('w')               # shorthand
poly = Polynomial(Monomial('w'))     # longer, equivalent

Create polynomial with two monomials and lists of deltas:

poly = Polynomial(('m', (0, 1)), ('w', (0, 0), (1, 1)))

Parameters:

Name	Type	Description	Default
monomials	Optional[Union[str, Monomial, Tuple[str, DELTAS]]]	arbitrary monomials.	()

some_infty property

some_infty: bool

True if some monomial yields an infinity choice.

add

add(polynomial: Polynomial) -> Polynomial

Add two polynomials.

• If both lists are empty the result is empty.
• If one list is empty, the result will be the other list of polynomials.

Otherwise, the operation will zip the two lists together and return a new polynomial of sorted monomials.

Parameters:

Name	Type	Description	Default
polynomial	Polynomial	Polynomial to add to self.	required

Returns:

Type	Description
Polynomial	New, sorted polynomial that is a sum of the two input polynomials.

choice_scalar

choice_scalar(*choices: int, least_scalar: str = None) -> Optional[str]

For given sequence of choices, determine corresponding scalar.

Parameters:

Name	Type	Description	Default
choices	int	tuple of choices.	()
least_scalar	str	typically zero, but can be m on the diagonal.	None

Returns:

Type	Description
Optional[str]	Scalar value matching choices or None.

compare staticmethod

compare(delta_list1: list, delta_list2: list) -> Comparison

Compare 2 lists of deltas.

We compare the initial segment up to the size of the shortest one. If the initial segments match, then the result is determined based on length. Three outputs are possible:

• SMALLER if the first list is smaller than the second
• EQUAL if both lists are equal in contents and length
• LARGER if the first list is larger than the second

The return value represents the relation of first list to the second one. Smaller means either

• delta values of first list are smaller -or-
• deltas are equal but first list is shorter.

Larger is the opposite case.

Parameters:

Name	Type	Description	Default
delta_list1	list	first monomial list to compare.	required
delta_list2	list	second monomial list to compare.	required

Returns:

Type	Description
Comparison	Result of comparison.

copy

copy() -> Polynomial

Make a deep copy of polynomial.

equal

equal(polynomial: Polynomial) -> bool

Determine if two polynomials are equal.

This method will compare current polynomial (self) to another polynomial provided as argument. Result of true means both polynomials have an equal number of monomials, and element-wise each monomial has the same list of deltas. Otherwise, the result is false.

This method is alias of == operator.

Parameters:

Name	Type	Description	Default
polynomial	Polynomial	polynomial to compare.	required

Returns:

Type	Description
bool	True if polynomials are equal and false otherwise.

eval

eval(*scalars: str) -> List[DELTAS]

List of monomial deltas with scalar in *scalars. Scalars always includes \(\infty\), but can include other flows.

from_scalars staticmethod

from_scalars(index: int, *scalars: str) -> Polynomial

Build a polynomial of multiple monomials with deltas.

Example

For arguments index=5 and scalars= m, w, p, the method returns a Polynomial equal to:

m1 = Monomial('m', (0, 5))
m2 = Monomial('w', (1, 5))
m3 = Monomial('p', (2, 5))

Polynomial(m1, m2, m3)

Parameters:

Name	Type	Description	Default
index	int	Delta index.	required
scalars	str	Scalar values.	()

Returns:

Type	Description
Polynomial	Generated polynomial.

inclusion staticmethod

inclusion(list_monom: list, mono: Monomial, i: int = 0) -> Tuple[bool, int]

Filter list_monom regarding mono inclusion and return info.

Remove all monomials of list_monom that are included in mono.

Return CONTAINS if one of monomials of list_monom contains mono (regarding Monomial.inclusion def).

Parameters:

Name	Type	Description	Default
list_monom	list	A list of monomials.	required
mono	Monomial	A monomial we want to add.	required
i	int	The position index where to add mono.	0

Returns:

Type	Description
Tuple[bool, int]	False if mono already in list_monom and shifted index where to insert mono, return True if mono not in list_monom.

remove_zeros

remove_zeros() -> Polynomial

Removes all encountered 0s from a polynomial.

Before returning, if the list is empty, the result produces a 0-monomial.

Returns:

Type	Description
Polynomial	polynomial with list of monomials for which zeros are
Polynomial	removed, unless 0 is the only monomial.

show

show() -> None

Display polynomial.

sort_monomials staticmethod

sort_monomials(monomials: list) -> list

Given a list of monomials this method will return them in order.

The sort is performed by first dividing the list of monomials into halves recursively until each half contains at most one monomial. Then the sort will begin to combine (or zip) the halves into a sorted list.

The sort performs comparison of deltas, and orders the monomials based on the delta values. If two monomials have the same deltas, we compute new scalar value, and if it is not 0, we keep the result monomial. Note that if we get 2 monomials with same deltas, and only at most 1 is kept, with possibly updated scalar. This means sort can return a result that is shorter than the input argument.

The original list argument is not mutated by this sort operation, i.e. this is not sort in place.

Parameters:

Name	Type	Description	Default
monomials	list	list of monomials to sort.	required

Returns:

Type	Description
list	list of sorted monomials.

times

times(polynomial: Polynomial) -> Polynomial

Multiply two polynomials.

Here we assume at least self is a sorted polynomial, and the result of this operation will be sorted.

This operation works as follows:

1. We compute a table of all the separated products \(P.m_1,...,P.m_n\). Each of the elements is itself a sorted list of monomials: \(P.m_j=m^j_1,...,m^j_k\)

2. We then sort the list of the first (smallest) elements of each list. I.e. we sort the list \(m^1_1,m^2_1,...,m^n_1\) and produce the list corresponding list of indexes of length n, I.e. a permutation over \({0,...,n}\).

3. Once all this preparatory operations are done, the main part of the algorithm goes as follows:

4. We consider the first element — say j — of the list of indexes and append to the result the first element of the corresponding list \(P.m_j\) of monomials.

5. We remove both the first element of the list of index and the first element of \(P.m_j\).

6. If \(P.m_j\) is not empty, we insert j in the list of index at the right position: for this we compare the (new) first element of \(P.m_j\) to \(m^{i_2}_1\) (as we removed the first element, \(i_2\) is now the head of the list of indexes), then \(m^{i_3}_1\), until we reach the index h such that \(m^{i_h}_1\) is larger than \(m^{j}_1\).

7. We start back at point 4. Unless only one element is left in the list of indexes. In this case, we simply append the tail of the corresponding list to the result.

Parameters:

Name	Type	Description	Default
polynomial	Polynomial	polynomial to multiply with self.	required

Returns:

Type	Description
Polynomial	A new polynomial that is the sorted product of the two input polynomials.