opt_einsum.paths.greedy

opt_einsum.paths.greedy(inputs, output, size_dict, memory_limit=None, choose_fn=None, cost_fn='memory-removed')[source]

Finds the path by a three stage algorithm:

  1. Eagerly compute Hadamard products.
  2. Greedily compute contractions to maximize removed_size
  3. Greedily compute outer products.

This algorithm scales quadratically with respect to the maximum number of elements sharing a common dim.

Parameters:
  • inputs (list) – List of sets that represent the lhs side of the einsum subscript
  • output (set) – Set that represents the rhs side of the overall einsum subscript
  • size_dict (dictionary) – Dictionary of index sizes
  • memory_limit (int) – The maximum number of elements in a temporary array
  • choose_fn (callable, optional) – A function that chooses which contraction to perform from the queu
  • cost_fn (callable, optional) – A function that assigns a potential contraction a cost.
Returns:

path – The contraction order (a list of tuples of ints).
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)
[(0, 2), (0, 1)]