Contraction order optimization

The @ein_str string literal does not optimize the contraction order for more than two input tensors.

julia> using OMEinsum
julia> code = ein"ij,jk,kl,li->"ij, jk, kl, li ->

The return value is a StaticEinCode object that does not contain a contraction order. The time and space complexity can be obtained by calling the contraction_complexity function.

julia> size_dict = uniformsize(code, 10)  # size of the labels are set to 10Dict{Char, Int64} with 4 entries:
  'j' => 10
  'i' => 10
  'k' => 10
  'l' => 10
julia> contraction_complexity(code, size_dict)  # time and space complexityTime 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.

Optimizing the contraction order

To optimize the contraction order, we can use the optimize_code function.

julia> optcode = optimize_code(code, size_dict, TreeSA())SlicedEinsum{Char, DynamicNestedEinsum{Char}}(Char[], kl, kl ->
├─ jk, lj -> kl
│  ├─ jk
│  └─ li, ij -> lj
│     ├─ li
│     └─ ij
└─ kl
)

The output value is a binary contraction tree with type SlicedEinsum or NestedEinsum. The TreeSA is a local search algorithm that optimizes the contraction order. More algorithms can be found in the OMEinsumContractionOrders and the performance tips of GenericTensorNetworks.

After optimizing the contraction order, the time and readwrite complexities are significantly reduced.

julia> contraction_complexity(optcode, size_dict)Time complexity: 2^11.036173612553485
Space complexity: 2^6.643856189774724
Read-write complexity: 2^9.64565843240871

Using optein string literal

For convenience, the optimized contraction can be directly contructed by using the @optein_str string literal.

julia> optein"ij,jk,kl,li->"  # optimized contraction, without knowing the size of the tensorsjk, jk ->
├─ jk
└─ ij, ik -> jk
   ├─ ij
   └─ li, kl -> ik
      ├─ li
      └─ kl

The drawback of using @optein_str is that the contraction order is optimized without knowing the size of the tensors. Only the tensor ranks are used to optimize the contraction order.

Manual optimization

One can also manually specify the contraction order by using the @ein_str string literal.

julia> ein"((ij,jk),kl),li->ik"  # manually optimized contractionikl, li -> ik
├─ ik, kl -> ikl
│  ├─ ij, jk -> ik
│  │  ├─ ij
│  │  └─ jk
│  └─ kl
└─ li