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:

enter image description here

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$:

enter image description here

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"

  • $\begingroup$ Try dynamic programming on subtrees. $\endgroup$ Dec 14, 2021 at 21:22
  • $\begingroup$ @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 $\endgroup$ Dec 14, 2021 at 21:29
  • $\begingroup$ 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. $\endgroup$ Dec 14, 2021 at 22:53
  • $\begingroup$ 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.. $\endgroup$ Dec 14, 2021 at 23:31
  • $\begingroup$ someone suggested this paper -- it claims some progress towards polynomial algorithm for this problem dr.ntu.edu.sg/bitstream/10356/141943/2/… $\endgroup$ Dec 15, 2021 at 0:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.