# Generalizing Matrix Chain problem: optimal summation in a tree

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"

• Try dynamic programming on subtrees. Dec 14, 2021 at 21:22
• @YuvalFilmus so if the naive approach of creating a message for every subtree is the best possible, this would make it a $2^{O(n)}$ problem Dec 14, 2021 at 21:29
• I don't think so. There should be a lot fewer subtrees. Consider what happens in the case of a path, which corresponds to the usual problem. Dec 14, 2021 at 22:53
• For the $O(n^3)$ alg in the case of path, we compute cost for each of the $n^2$ connected subgraphs, but here we have at least $2^{2^{D-1}}$ connected subgraphs.. Dec 14, 2021 at 23:31
• someone suggested this paper -- it claims some progress towards polynomial algorithm for this problem dr.ntu.edu.sg/bitstream/10356/141943/2/… Dec 15, 2021 at 0:53