polynomials_on_simplices.algebra.multiindex module

Operations on multi-indices (elements of \(\mathbb{N}_0^n\)).

class MultiIndex(*components)

Bases: object

A multi-index (element of \(\mathbb{N}_0^n\)).

This class defines the basic algebraic operations on multi-indices:

Addition:

\[+ : \mathbb{N}_0^n \times \mathbb{N}_0^n \to \mathbb{N}_0^n,\]

\[\alpha + \beta = (\alpha_1 + \beta_1, \alpha_2 + \beta_2, \ldots, \alpha_n + \beta_n).\]

Power:

\[\operatorname{pow} : R^n \times \mathbb{N}_0^n \to R,\]

\[\operatorname{pow}(x, \alpha) \equiv x^{\alpha} = x_1^{\alpha_1} x_2^{\alpha_2} \ldots x_n^{\alpha_n},\]

where \(R\) is any ring.

Parameters:components (int or Iterable[int]) – Component(s) (indices) for the multi-index.

components()

Multi-index components/indices.

Returns:The multi-index components. Return type:tuple[int]

to_tuple()

Multi-index converted to a tuple.

Returns:Tuple containing the multi-index components (indices). Return type:tuple[int]

class MultiIndexIterator(n, r)

Bases: object

Iterate over all n-dimensional multi-indices with norm <= r.

Parameters:

• n (int) – Dimension of the multi-indices we iterate over.
• r (int) – Maximum norm of the multi-indices we iterate over.

next()

Proceed to next multi-index.

class MultiIndexIteratorMultiCap(n, r)

Bases: object

Iterate over all n-dimensional multi-indices with satisfying a_i <= r_i.

Parameters:

• n (int) – Dimension of the multi-indices we iterate over.
• r (Iterable[int]) – Maximum value for each component of the multi-indices we iterate over.

next()

Proceed to next multi-index.

binom(a, b)

Binomial coefficient of two multi-indices, a over b,

\[\binom{a}{b} = \frac{a!}{b!(a - b)!}.\]

See factorial().

Parameters:

• a – Multi-index.
• b – Multi-index.

Returns:

a choose b.

Return type:

int

exact_norm_to_general(a)

Conversion of a multi-index from exact to general form.

Convert an n-dimensional exact multi-index to a general n-1-dimensional multi-index by removing the first number in the multi-index (exact meaning that the multi-index has norm r).

Parameters:a – Multi-index. Returns:Multi-index. Return type:MultiIndex

factorial(a)

Factorial of a multi-index, \(a! = a_1! a_2! \ldots a_n!\).

Parameters:a – Multi-index. Returns:Factorial of the multi-index.

general_to_exact_norm(a, r)

Conversion of a multi-index from general to exact form.

Convert a general n-dimensional multi-index to an exact n+1-dimensional multi-index (exact meaning that the multi-index has norm r). Let \(a \in \mathbb{N}_0^n\). Then this function returns \(b \in \mathbb{N}_0^{n + 1}\) with \(b_1 = r - |a|\) and \(b_i = a_{i - 1}, i = 2, 3, \ldots, n + 1\).

Parameters:

• a – Multi-index.
• r (int) – Desired norm of exact multi-index.

Returns:

Multi-index with norm r.

Return type:

MultiIndex

Examples

>>> general_to_exact_norm((1, 2), 4).to_tuple()
(1, 1, 2)
>>> general_to_exact_norm((0, 0), 2).to_tuple()
(2, 0, 0)

generate(n, r, i)

Generate the i:th multi-index in the sequence of all n-dimensional multi-indices with norm <= r.

There is a natural ordering of the multi-indices in the sense that a multi-index \(a\) of norm <= r can be identified with a natural number \(n(a)\) by \(n(a) = \sum_{k = 0}^{\dim \nu} a_k r^k\) (interpreting the indices of a as digits of a number in base r), and this number is strictly increasing with i.

Parameters:

• n (int) – Dimension of multi-indices.
• r (int) – Maximum norm of multi-indices.
• i (int) – Which multi-index to generate. Need to be in the range [0, num_multiindices(n, r) - 1].

Returns:

The i:th multi-index.

Return type:

MultiIndex

generate_all(n, r)

Generate the sequence of all n-dimensional multi-indices with norm <= r.

For ordering of the multi-indices see generate().

Parameters:

• n (int) – Dimension of multi-indices.
• r (int) – Maximum norm of multi-indices.

Returns:

List of all multi-indices.

Return type:

List[MultiIndex].

generate_all_exact_norm(n, r)

Generate all n-dimensional multi-indices with norm r.

Parameters:

• n (int) – Dimension of multi-indices.
• r – Norm of each multi-index.

Returns:

List of all multi-indices with norm r.

Return type:

List[MultiIndex].

generate_all_increasing(n, r)

Generate all increasing (see is_increasing()) n-dimensional multi-indices such that each component is less than or equal to r.

Parameters:

• n (int) – Dimension of multi-indices.
• r – Max value for each component of the multi-indices.

Returns:

List of increasing multi-indices.

Return type:

List[MultiIndex].

generate_all_multi_cap(r)

Generate all n-dimensional multi-indices \(a\) such that \(a_i \leq r_i, i = 1, 2, \ldots, n\), where n is the length of r.

Parameters:r (Iterable[int]) – Maximum value for each entry of the multi-indices. Returns:List of all multi-indices. Return type:List[MultiIndex].

generate_all_non_decreasing(n, r)

Generate all non-decreasing (see is_non_decreasing()) n-dimensional multi-indices such that each component is less than or equal to r.

Parameters:

• n (int) – Dimension of multi-indices.
• r – Max value for each component of the multi-indices.

Returns:

List of non-creasing multi-indices.

Return type:

List[MultiIndex].

generate_multi_cap(r, i)

Generate the i:th multi-index among all n-dimensional multi-indices \(a\) such that \(a_i \leq r_i, i = 1, 2, \ldots, n\), where n is the length of r.

The ordering of the multi-indices is natural in the sense that each generated multi-index can be identified with a natural number expressed in the base \(\max_i r_i\), and this number is strictly increasing with i.

Parameters:

• r (Iterable[int]) – Maximum value for each entry of the multi-indices.
• i (int) – Which multi-index to generate. Need to be in the range [0, \((\Pi_i (r_i + 1)) - 1\)].

Returns:

The i:th multi-index.

Return type:

MultiIndex

get_index(mi, r)

Get the index of a multi-index in the sequence of all multi-indices of the same dimension and with norm <= r (as given by generate_all()).

Parameters:

• mi – Multi-index.
• r (int) – Maximum norm of multi-indices.

Returns:

Index of multi-index.

Return type:

int

Raise:

ValueError if the given multi-index doesn’t belong to the sequence of multi-indices with the specified dimension and with norm <= r.

is_increasing(a)

Check if the indices of a multi-index form an increasing sequence, i.e. \(a_i < a_j\) if \(i < j\).

Parameters:a – Multi-index. Returns:Whether or not the indices of the multi-index are increasing.

Examples

>>> is_increasing((1, 2, 3))
True
>>> is_increasing((1, 1))
False

is_non_decreasing(a)

Check if the indices of a multi-index form a non-decreasing sequence, i.e. \(a_i \leq a_j\) if \(i < j\).

Parameters:a – Multi-index. Returns:Whether or not the indices of the multi-index are non-decreasing.

Examples

>>> is_non_decreasing((1, 2, 3))
True
>>> is_non_decreasing((1, 1))
True
>>> is_non_decreasing((1, 3, 2))
False

multinom(a)

Multinomial coefficient of a multi-index.

Number of ways to put \(|a|\) elements in n boxes with \(a_i\) elements in box i (where n is the number of elements in \(a\)),

\[\binom{|a|}{a} = \frac{|a|!}{a!}.\]

Parameters:a – Multi-index. Returns:Multinomial coefficient, \(\frac{|a|!}{a!}\).

multinom_general(r, a)

Multinomial coefficient of a multi-index.

Number of ways to put \(r\) elements in n boxes with \(a_i\) elements in box i, \(i = 1, 2, \ldots, n - 1\) and \(r - |a|\) elements in box n (where n - 1 is the number of elements in \(a\)),

\[\binom{r}{a} = \frac{r!}{a!(r - |a|)!}.\]

This is equal to the multinomial coefficient of the multi-index a converted to exact form with norm r.

Parameters:

• a – Multi-index.
• r (int) – Total number of elements (or norm of the exact multi-index).

Returns:

Multinomial coefficient, \(\frac{r!}{a!(r - |a|)!}\).

norm(a)

Absolute value of a multi-index, \(|a| = a_1 + a_2 + \ldots + a_n\).

Parameters:a – Multi-index. Returns:Absolute value of the multi-index.

num_multiindices(n, r)

Compute the number of n-dimensional multi-indices with norm <= r.

Parameters:

• n (int) – Dimension of multi-indices.
• r (int) – Maximum norm of multi-indices.

Returns:

Number of unique multi-indices.

Return type:

int

power(x, a)

Raise a vector to the power of a multi-index, \(x^a = x_1^{a_1} x_2^{a_2} \ldots x_n^{a_n}\).

Parameters:

• x – Iterable of same length as the multi-index a.
• a – Multi-index.

Returns:

x raised to the power a.

random_multiindex(n, r)

Generate a random multi-index from the set of all n-dimensional multi-indices with norm <= r, with uniform sampling.

Parameters:

• n (int) – Dimension of multi-index.
• r (int) – Maximum norm of multi-index.

Returns:

Random n-dimensional multi-index with norm <= r.

Return type:

MultiIndex

unit_multiindex(n, i)

Generate the n-dimensional multi-index (element of \(\mathbb{N}_0^n\)) with all entries equal to zero except the i:th entry which is equal to 1.

Parameters:

• n (int) – Dimension of the multi-index.
• i (int) – Entry of the multi-index which should be equal to 1.

Returns:

The i:th n-dimensional unit multi-index.

Return type:

MultiIndex

Examples

>>> print(unit_multiindex(3, 0))
(1, 0, 0)
>>> print(unit_multiindex(2, 1))
(0, 1)

zero_multiindex(n)

Generate the n-dimensional zero multi-index (element of \(\mathbb{N}_0^n\) with all entries equal to zero).

Parameters:n (int) – Dimension of the multi-index. Returns:The n-dimensional zero multi-index. Return type:MultiIndex

Examples

>>> print(zero_multiindex(2))
(0, 0)