`numpy._core.einsumfunc:_greedy_path`

source: /numpy/_core/einsumfunc.py :330

Signature

def _greedy_path ( input_sets , output_set , idx_dict , memory_limit )

Summary

Finds the path by contracting the best pair until the input list is exhausted. The best pair is found by minimizing the tuple (-prod(indices_removed), cost). What this amounts to is prioritizing matrix multiplication or inner product operations, then Hadamard like operations, and finally outer operations. Outer products are limited by memory_limit. This algorithm scales cubically 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 : list: The greedy contraction order within the memory limit constraint.

Examples

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

Aliases

numpy._core.einsumfunc._greedy_path