Matrix Chain Problem can be viewed as the problem of finding the optimal summation order in a path-structured tensor network. How hard is the problem if we extend it to trees?
For instance, take the following sum, written in Einstein summation notation $$A_i B^i_j C^j_k D^k$$
This corresponds to the tensor network below:
There are 3 edges $e$, corresponding to indices $i,j,k$, each with their own dimension $d_e$. One possible summation order is below:
$$((A_i B_j^i) C_k^j) D^k$$
The number of multiplications, aka, total cost of this order is
$$d_i\times d_j + d_j\times d_k + d_k$$
Given a list of dimensions $\{d_e\}$, finding the order which minimizes total cost is equivalent to the Matrix Chain problem, solvable in $n \log n$ time (wikipedia).
Take the following sum in Einstein summation notation:
$$A_{ij}B^{i}_{kl}C^j_{mn}D^k E^l F^m G^n$$
This corresponds to the tensor network below, binary tree of depth $D=3$:
There are 6 edges $e$, each corresponding to an index of dimension $d_e$. One way of computing the sum is the breadth-first search order
$$(((((A_{ij}B^{i}_{kl})C^j_{mn})D^k) E^l) F^m) G^n$$
Each step is a contraction of two tensors, requiring the number of multiplications which is the product of dimensions of all indices occurring in either tensor. IE, cost of computing $Y_i^l=X_{ijk}Y^{jkl}$ is $d_i\times d_j\times d_k\times d_l$.
Total cost of computing this sum in breadth-first search order is $$d_j\times d_i\times d_k \times d_l +d_k\times d_l\times d_j\times d_m\times d_n+d_k\times d_l \times d_m \times d_n + d_l \times d_m \times d_n +d_m\times d_n + d_n$$
For a tensor network with $n$ tensors, forming a complete binary tree of depth $D$, given a list of dimensions $\{d_e\}$, what is the complexity of finding an order which minimizes total cost?
PS: if we allow leaves to have free indices (ie, dangling edges in this graph), this kind of representation is an instance of "Hierarchical Tucker Decomposition"
