opt_einsum.contract_path

opt_einsum.contract_path(*operands, **kwargs)

Find a contraction order ‘path’, without performing the contraction.

Parameters

• subscripts (str) – Specifies the subscripts for summation.

• *operands (list of array_like) – These are the arrays for the operation.

• optimize (str, list or bool, optional (default: auto)) – Choose the type of path.

  • if a list is given uses this as the path.

  • 'optimal' An algorithm that explores all possible ways of contracting the listed tensors. Scales factorially with the number of terms in the contraction.

  • 'branch-all' An algorithm like optimal but that restricts itself to searching ‘likely’ paths. Still scales factorially.

  • 'branch-2' An even more restricted version of ‘branch-all’ that only searches the best two options at each step. Scales exponentially with the number of terms in the contraction.

  • 'greedy' An algorithm that heuristically chooses the best pair contraction at each step.

  • 'auto' Choose the best of the above algorithms whilst aiming to keep the path finding time below 1ms.

• use_blas (bool) – Use BLAS functions or not

• memory_limit (int, optional (default: None)) – Maximum number of elements allowed in intermediate arrays.

• shapes (bool, optional) – Whether contract_path should assume arrays (the default) or array shapes have been supplied.

Returns

• path (list of tuples) – The einsum path

• PathInfo (str) – A printable object containing various information about the path found.

Notes

The resulting path indicates which terms of the input contraction should be contracted first, the result of this contraction is then appended to the end of the contraction list.

Examples

We can begin with a chain dot example. In this case, it is optimal to contract the b and c tensors represented by the first element of the path (1, 2). The resulting tensor is added to the end of the contraction and the remaining contraction, (0, 1), is then executed.

>>> a = np.random.rand(2, 2)
>>> b = np.random.rand(2, 5)
>>> c = np.random.rand(5, 2)
>>> path_info = opt_einsum.contract_path('ij,jk,kl->il', a, b, c)
>>> print(path_info[0])
[(1, 2), (0, 1)]
>>> print(path_info[1])
  Complete contraction:  ij,jk,kl->il
         Naive scaling:  4
     Optimized scaling:  3
      Naive FLOP count:  1.600e+02
  Optimized FLOP count:  5.600e+01
   Theoretical speedup:  2.857
  Largest intermediate:  4.000e+00 elements
-------------------------------------------------------------------------
scaling                  current                                remaining
-------------------------------------------------------------------------
   3                   kl,jk->jl                                ij,jl->il
   3                   jl,ij->il                                   il->il

A more complex index transformation example.

>>> I = np.random.rand(10, 10, 10, 10)
>>> C = np.random.rand(10, 10)
>>> path_info = oe.contract_path('ea,fb,abcd,gc,hd->efgh', C, C, I, C, C)

>>> print(path_info[0])
[(0, 2), (0, 3), (0, 2), (0, 1)]
>>> print(path_info[1])
  Complete contraction:  ea,fb,abcd,gc,hd->efgh
         Naive scaling:  8
     Optimized scaling:  5
      Naive FLOP count:  8.000e+08
  Optimized FLOP count:  8.000e+05
   Theoretical speedup:  1000.000
  Largest intermediate:  1.000e+04 elements
--------------------------------------------------------------------------
scaling                  current                                remaining
--------------------------------------------------------------------------
   5               abcd,ea->bcde                      fb,gc,hd,bcde->efgh
   5               bcde,fb->cdef                         gc,hd,cdef->efgh
   5               cdef,gc->defg                            hd,defg->efgh
   5               defg,hd->efgh                               efgh->efgh