# 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. Commented 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 Commented 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. Commented 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.. Commented 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/… Commented Dec 15, 2021 at 0:53

If you restrict yourself to linear contraction orders, i.e., you only contract tensors adjacent to the set of already-contracted ones, you can actually do this in polynomial time. I have recently proved this in my Master's thesis. The result follows from a fascinating yet non-trivial connection to database join ordering (I recommend these slides for join ordering). I also have a preprint, but the thesis explains it properly.

If you want general contraction orders, i.e., you contract any two adjacent tensors, this is still an open problem (I learned this from the author of Xu et. al; that is also the reason they optimized for a weaker cost function, i.e., minimizing the largest intermediate tensor). Actually, the situation is similar in join ordering: the problem for tree queries is still open (Moerkotte et al.).

However, you can provide near-optimal general contraction orders for trees. The key idea is to regard the linear order of the optimal algorithm as a chain and run the textbook cubic-time dynamic programming to build the optimal contraction tree given that order. This idea was first explored in Neumann et al. (linearized dynamic programming) and has been shown to provide near-optimal solutions. Beyond the optimality result, I empirically validated that this holds for tensor networks as well. Recently, Ibrahim et al. proposed the same approach, but their linearization, i.e., the permutation of the leaves, is chosen greedily. The advantage of having an optimal algorithm for the linearization is that you are at least optimal in the regime of linear orders, so you can provide robustness that a greedy algorithm cannot.

You can find implementations of these algorithms here: https://github.com/stoianmihail/netzwerk

• Thanks for the in-depth response! Connection to database join problem is useful to know Commented May 30, 2023 at 18:18

Unfortunately, there are some small issues with the recent pre-print by Xu et al., NP-Hardness of Tensor Network Contraction Ordering:

(1) Finding the minimal operation cost (like you describe) is NP hard, even for trees.

a. First, in their proof of Thm. 7, they allow tensor outer products. Namely, they argue that they need to find the optimal contraction sequence $$V_1, \ldots, V_n$$. However these are not connected in the original tree tensor network. Indeed, in their chosen TN shape, only the tensor $$V_0$$ is connected to the rest.

When one allows outer products in the contraction steps, the problem becomes the most general one, which is, of course, NP-hard. The intuition is that you obtain a clique tensor network, in which every tensor is allowed to be contracted with any other.

b. Second, the shape of their chosen tree TN is also not particularly useful. That's called a star graph. For such a shape, any general contraction tree is, by construction, a linear contraction tree, because $$V_0$$ must be the first leaf in the contraction tree. Hence, this kind of TTNs can be solved optimally by TensorIKKBZ (Stoian et al.).

That being said:

The problem of whether tensor contraction ordering is NP-hard for Tree Tensor Networks for the total contraction cost still remains open.

P.S. I'm actually advising a master's thesis for this problem for the equivalent problem in join ordering.

(2) Finding the contraction order, even for the single most expensive contraction, is NP hard, even in trees.

Actually, there is no difference between finding the contraction order or its corresponding cost. Indeed, they still claim that this can be done in polynomial time (by referring to their work).

The paper NP-Hardness of Tensor Network Contraction Ordering (by Jianyu Xu, Hanwen Zhang, Ling Liang, Lei Deng, Yuan Xie, Guoqi Li) shows that

(1) Finding the minimal operation cost (like you describe) is NP hard, even for trees.

The paper you linked Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees (by most of the same authors) instead considered the problem of minimizing the "single most expensive contraction". This was shown to be polynomial.

However, the new paper by Xu et al shows:

(2) Finding the contraction order, even for the single most expensive contraction, is NP hard, even in trees.