multi_index#

A module with JIT-compiled utility functions to process and manipulate multi-index set of exponents.

Notes

All multi-index sets of exponents are always assumed to be two-dimensional non-negative integer arrays. There is no explicit check of this conditions in the following functions.

minterpy.jit_compiled.multi_index.cross_and_sum(indices_1, indices_2)[source]#

Create a cross product of multi-indices and sum the pairs.

Parameters:

indices_1 (numpy.ndarray) – First two-dimensional integers array of multi-indices.
indices_2 (numpy.ndarray) – Second two-dimensional integers array of multi-indices.

Returns:

An array that contains the pair-wise sums of cross-products between the two array.

Return type:

numpy.ndarray

Notes

The two arrays must have the same number of columns.

minterpy.jit_compiled.multi_index.unique_indices(indices)[source]#

Get the boolean mask of unique elements from an array of multi-indices.

Parameters:: indices (numpy.ndarray) – Two-dimensional integer array of multi-indices to process.
Returns:: A boolean mask array that indicates unique elements from the input array.
Return type:: numpy.ndarray

Notes

The input multi-indices must already be lexicographically sorted.
It turns out that getting the unique elements from a two-dimensional array is expensive, more than sorting lexicographically large array.

minterpy.jit_compiled.multi_index.is_lex_smaller_or_equal(index_1, index_2)[source]#

Check if an index is lexicographically smaller than or equal to another.

Parameters:

index_1 (numpy.ndarray) – A given multi-index, a one-dimensional array of length m.
index_2 (numpy.ndarray) – Another multi-index, a one dimensional array of length m.

Returns:

Return True if index_1 <= index_2 lexicographically, otherwise False.

Return type:

bool

Notes

By default, Numba disables the bound-checking for performance reason. Therefore, if the two input arrays are of inconsistent shapes, no exception will be raised and the results cannot be trusted.

Examples

>>> my_index_1 = np.array([1, 2, 3])  # "Reference index"
>>> my_index_2 = np.array([1, 2, 3])  # Equal
>>> is_lex_smaller_or_equal(my_index_1, my_index_2)
True
>>> my_index_3 = np.array([2, 4, 5])  # Larger
>>> is_lex_smaller_or_equal(my_index_1, my_index_3)
True
>>> my_index_4 = np.array([0, 3, 2])  # Smaller
>>> is_lex_smaller_or_equal(my_index_1, my_index_4)
False

minterpy.jit_compiled.multi_index.is_lex_sorted(indices)[source]#

Check if an array of multi-indices is lexicographically sorted.

Parameters:: indices (numpy.ndarray) – Array of multi-indices, a two-dimensional non-negative integer array of shape (N, m), where N is the number of multi-indices and m is the number of spatial dimensions.
Returns:: True if the multi-indices is lexicographically sorted, and False otherwise
Return type:: bool

Notes

If there are any duplicate entries (between rows), an array of multi-indices does not have a lexicographical ordering.

Examples

>>> my_indices = np.array([[0, 2, 0]])  # single entry
>>> is_lex_sorted(my_indices)
True
>>> my_indices = np.array([[0, 0], [1, 0], [0, 2]])  # already sorted
>>> is_lex_sorted(my_indices)
True
>>> my_indices = np.array([[1, 0], [0, 0], [0, 2]])  # unsorted
>>> is_lex_sorted(my_indices)
False
>>> my_indices = np.array([[0, 0], [2, 0], [2, 0]])  # duplicate entries
>>> is_lex_sorted(my_indices)
False

minterpy.jit_compiled.multi_index.search_lex_sorted(indices, index)[source]#

Find the position of a given entry within an array of multi-indices.

Parameters:

indices (numpy.ndarray) – Array of lexicographically sorted multi-indices, a two-dimensional non-negative integer array of shape (N, m), where N is the number of multi-indices and m is the number of spatial dimensions.
index (numpy.ndarray) – Multi-index entry to check in indices. The element is represented by a one-dimensional array of length m, where m is the number of spatial dimensions.

Returns:

If index is present in indices, its position in indices is returned (the row number). Otherwise, a global constant NOT_FOUND is returned instead.

Return type:

int

Notes

indices must be lexicographically sorted.
This function is a binary search implementation that exploits a lexicographically sorted array of multi-indices. The time complexity of the implementation is \(O(m\log{N})\).
By Minterpy convention, duplicate entries are not allowed in a lexicographically sorted multi-indices. However, having duplicate entries won’t stop the search. In that case, the search returns the position of the first match but cannot guarantee which one is that from the duplicates.

Examples

>>> my_indices = np.array([
... [0, 0, 0],  # 0
... [1, 0, 0],  # 1
... [2, 0, 0],  # 2
... [0, 0, 1],  # 3
... ])
>>> my_index_1 = np.array([2, 0, 0])  # is present in my_indices
>>> search_lex_sorted(my_indices, my_index_1)
2
>>> my_index_2 = np.array([0, 1, 0])  # is not present in my_indices
>>> search_lex_sorted(my_indices, my_index_2)
-1

minterpy.jit_compiled.multi_index.is_index_contained(indices, index)[source]#

Check if a multi-index entry is present in a set of multi-indices.

Parameters:

indices (numpy.ndarray) – Array of lexicographically sorted multi-indices, a two-dimensional non-negative integer array of shape (N, m), where N is the number of multi-indices and m is the number of spatial dimensions.
index (numpy.ndarray) – Multi-index entry to check in the set. The element is represented by a one-dimensional array of length m, where m is the number of spatial dimensions.

Returns:

True if the entry index is contained in the set indices and False otherwise.

Return type:

bool

Notes

The implementation is based on the binary search and therefore indices must be lexicographically sorted.

Examples

>>> my_indices = np.array([
... [0, 0, 0],  # 0
... [1, 0, 0],  # 1
... [2, 0, 0],  # 2
... [0, 0, 1],  # 3
... ])
>>> is_index_contained(my_indices, np.array([1, 0, 0]))  # is present
True
>>> is_index_contained(my_indices, np.array([0, 1, 2]))  # is not present
False

minterpy.jit_compiled.multi_index.all_indices_are_contained(subset_indices, indices)[source]#

Checks if a set of indices is a subset of (or equal to) another set of indices.

Parameters:

subset_indices (ndarray) – one set of multi indices.
indices (ndarray) – another set of multi indices.

Returns:

True if subset_indices is a subset or equal to indices, False otherwise.

Return type:

bool

Notes

Exploits the lexicographical order of the indices to abort early -> not testing all indices.

minterpy.jit_compiled.multi_index.fill_match_positions(larger_idx_set, smaller_idx_set, positions)[source]#

Finds matching positions (array indices) for multi index entries in two multi indices.

Parameters:

larger_idx_set – the larger set of multi indices
smaller_idx_set – the smaller set of multi indices
positions – an array with positions (array indices) of multi index entries in larger_idx_set` that matches each of the entry in smaller_idx_set.