Contraction order optimization

OMEinsum does not implicitly optimize the contraction order. Functionalities related to contraction order optimization are mostly defined in OMEinsumContractionOrders

Here, we provide an example, advanced uses can be found in OMEinsumContractionOrders and the performance tips of GenericTensorNetworks. Let us first consider the following contraction order

using OMEinsum

code = ein"ij,jk,kl,li->"

ij, jk, kl, li -> 

The time and space complexity can be obtained by calling the contraction_complexity function.

size_dict = uniformsize(code, 10)

contraction_complexity(code, size_dict)

Time complexity: 2^13.287712379549449
Space complexity: 2^0.0
Read-write complexity: 2^8.64745842645492

The return values are log2 values of the number of iterations, number of elements of the largest tensor and the number of elementwise read-write operations.

optcode = optimize_code(code, size_dict, TreeSA())

SlicedEinsum{Char, DynamicNestedEinsum{Char}}(Char[], lk, kl -> 
├─ jl, jk -> lk
│  ├─ ij, li -> jl
│  │  ├─ ij
│  │  └─ li
│  └─ jk
└─ kl
)

The output value is a binary contraction tree with type NestedEinsum type. The time and readwrite complexities are significantly reduced comparing to the direct contraction.

contraction_complexity(optcode, size_dict)

Time complexity: 2^11.036173612553485
Space complexity: 2^6.643856189774724
Read-write complexity: 2^9.64565843240871