Faster Implementation of Multi-Indices Multiplication

Multiplication of two multi-index sets involves:

• taking the cross-product of the sets
• summing each element of the cross-product paris
• taking only the unique elements
• sorting the set lexicographically.

Currently, this is achieved by the function minterpy.core.utils.multiply_indices() with the following main steps:

• expand the dimension of one of the set when necessary
• create a list of from the product of the two indices: list(product(indices_1, indices_2))
• compute the sum of each element of the product combination
• sort lexicographically the resulting array; this consists of two steps: take only unique element and then sort lexicographically

The current implementation tends to be slow for moderate size multi-index sets (either in length or width).

For instance multiplying A_{5, 5, 2.0} (\lvert B \rvert = 1203) with B_{7, 5, 1.0} (\lvert B \rvert = 792):

>>> mi_1 = mp.MultiIndexSet.from_degree(5, 5, 2.0)
>>> mi_2 = mp.MultiIndexSet.from_degree(7, 5, 1.0)
>>> %timeit mi_1 * mi_2
3 s ± 23.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

with a simple numba-based implementations, we may accelerate this a bit:

>>> %timeit mi_1 * mi_2
366 ms ± 1.32 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)