opt_einsum.paths.greedy¶

opt_einsum.paths.greedy(input_sets, output_set, idx_dict, memory_limit)[source]¶

Finds the path by contracting the best pair until the input list is exhausted. The best pair is found by minimizing the tuple (-removed_size, cost). What this amounts to is prioritizing inner product operations, matrix multiplication, then Hadamard like operations, and finally outer operations. Outer products are limited by memory_limit and are ignored until no other operations are available. This algorithm scales quadratically with respect to the number of elements in the list input_sets.

Parameters:	input_sets (list) – List of sets that represent the lhs side of the einsum subscript output_set (set) – Set that represents the rhs side of the overall einsum subscript idx_dict (dictionary) – Dictionary of index sizes memory_limit (int) – The maximum number of elements in a temporary array
Returns:	path – The greedy contraction order within the memory limit constraint.
Return type:	list

Examples

>>> isets = [set('abd'), set('ac'), set('bdc')]
>>> oset = set('')
>>> idx_sizes = {'a': 1, 'b':2, 'c':3, 'd':4}
>>> greedy(isets, oset, idx_sizes, 5000)
[(0, 2), (0, 1)]