4
$\begingroup$

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"

$\endgroup$
5
  • $\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

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.