# Einsum Expressions

Let's take an arbitrary tensor network like the following.

This graph is a graphical notation equivalent to the following equation.

\[\sum_{i j k l m n o p} A_{mi} B_{ijp} C_{jkn} D_{pkl} E_{mno} F_{ol}\]

A naïve implementation of this equation is easy to implement.

```
result = zero(reduce(promote_type, eltype.([A,B,C,D,E,F])))
for (i,j,k,l,m,n,o,p) in Iterators.product(1:I, 1:J, 1:K, 1:L, 1:M, 1:N, 1:O, 1:P)
result += A[m,i] * B[i,j,p] * C[j,k,n] * D[p,k,l] * E[m,n,o] * F[o,l]
end
```

But it has a cost of $\prod_\alpha \dim(\alpha)$ where $\alpha \in \{i,j,k,l,m,n,o,p\}$ which is of $\mathcal{O}(\exp(n))$ time complexity.

## Basic utilities

The `EinExpr`

type has a stable definition: it's secure to access its fields using the dot-syntax (e.g. `path.head`

), but we recommend to use the following methods instead. They provide a much more stable API and can be used in a functional manner.

`EinExprs.head`

— Function`EinExprs.args`

— Function`args(path::EinExpr)`

Return the children of the `path`

, which correspond to input tensors for the contraction step in the top of the `path`

.

See also: `head`

.

`args(sexpr::SizedEinExpr)`

**Note**

Unlike `args(::EinExpr)`

, this function returns `SizedEinExpr`

objects.

Missing docstring for `Base.size(::EinExpr)`

. Check Documenter's build log for details.

Some other useful methods are:

`Base.ndims`

— Method`ndims(path::EinExpr)`

Return the number of indices of the resulting tensor from contracting `path`

.

`EinExprs.inds`

— Function`EinExprs.suminds`

— Function`suminds(path)`

Indices of summation of an `EinExpr`

.

\[\mathtt{path} \equiv \sum_{j k l m n o p} A_{mi} B_{ijp} C_{jkn} D_{pkl} E_{mno} F_{ol}\]

`suminds(path) == [:j, :k, :l, :m, :n, :o, :p]`

`EinExprs.parsuminds`

— Function`parsuminds(path)`

Indices of summation of possible pairwise tensors contractions between children of `path`

.

`EinExprs.contractorder`

— Function`contractorder(path::EinExpr)`

Transform `path`

into a contraction order.

`EinExprs.select`

— Function`select(path::EinExpr, i)`

Return the child elements that contain `i`

indices.

`EinExprs.neighbours`

— Function`neighbours(path::EinExpr, i)`

Return the indices neighbouring to `i`

.

## Construction by summation

One option for constructing `EinExpr`

s manually is to use the `sum`

methods. For example, imagine that we have the following tensor equation and we want to contract first tensors $E_{mno}$ and $F_{ol}$. The resulting equation would be equivalent to adding a summatory to $E$ and $F$ as written in the right-hand side.

\[\sum_{i j k l m n o p} A_{mi} B_{ijp} C_{jkn} D_{pkl} E_{mno} F_{ol} = \sum_{i j k l m n p} A_{mi} B_{ijp} C_{jkn} D_{pkl} \sum_o E_{mno} F_{ol}\]

In `EinExprs`

, we advocate for code that it's *almost* as easy as writing math. As such, one can write `sum([E, F])`

to create a new `EinExpr`

where common indices are contracted or `sum!(path, :o)`

for the in-place version where $E$ and $F$ are children of `path`

.

`Base.sum!`

— MethodMissing docstring for `Base.sum(::EinExpr, ::Union{Symbol, Tuple{Vararg{Symbol}}, AbstractVector{<:Symbol}})`

. Check Documenter's build log for details.

In order to reverse the operation and unfix the contraction, the user may call the `collapse!`

function.

`EinExprs.collapse!`

— Function`collapse!(path::EinExpr)`

Collapses all sub-branches, merging all tensor leaves into the `args`

field.

`AbstractTrees`

integration

`EinExpr`

type integrates with the `AbstractTrees`

package in order to implement some of the tree-traversing algorithms. The interface is public and thus any user can use it to implement their own methods.

For example, the `AbstractTrees.Leaves`

function returns an iterator through the leaves of any tree; i.e. the initial tensors in our case. We implement the `Branches`

function in order to walk through the non-terminal nodes; i.e. the intermediate tensors.

`EinExprs.Branches`

— Function`Branches(path::EinExpr)`

Iterator that walks through the non-terminal nodes of the `path`

tree.

See also: `branches`

.

`EinExprs`

exports a variant of these methods which return collections.

`EinExprs.leaves`

— Function`leaves(path::EinExpr[, i])`

Return the terminal leaves of the `path`

, which correspond to the initial input tensors. If `i`

is specified, then only return the $i$-th tensor.

See also: `branches`

.

`EinExprs.branches`

— Function