3
$\begingroup$

Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order?

For example, take the following summation over 5 variables: $$\sum_{v1,v2,v3,v4,v5} f_1(v_1,v_5)f_2(v_1,v_2,v_3)f_3(v_3,v_4)f_4(v_2,v_4,v_5)$$

Each variable $vi$ takes integer values in $1\ldots di$ and factor $f(a,b,c)$ is a multidimensional array indexed by $a,b,c$. This is a tensor network because each variable occurs in exactly 2 factors, and we can represent it graphically by drawing factors as vertices and variables as edges in planar graph $G$

enter image description here

Given a sequence of variables, we eliminate variables in sequence order by summing out one variable at a time. For instance, starting with $v_1$, performing the first elimination reduces our problem to the following summation over 4 variables.

$$\sum_{v2,v3,v4,v5} f_*(v_2,v_3,v_5)f_3(v_3,v_4)f_4(v_2,v_4,v_5)$$

enter image description here

where $$f_*(v_2,v_3,v_5)=\sum_{v1}f_1(v_1,v_5)f_2(v_1,v_2,v_3)f_4(v_2,v_4,v_5)$$

The cost of this elimination was $d1\times d2 \times d3 \times d5$ which is the cost of computing $f_*$ (the new vertex created as we contract edge v1). As we continue this process we eventually end up with a scalar (another example). We get total cost by adding up costs of individual eliminations. Optimal elimination order minimizes total cost. What is the complexity of finding optimal elimination order?

Some known partial results

minimizing worst-step cost

Suppose every variable in the summation ranges from 1 to $d$. Then at least one elimination step has a cost $d^c$ where $c$ is the carving width of $G$. For planar graphs, the "ratcatcher" algorithm takes $O(n^3)$ time to find elimination order where the slowest step has cost $d^c$ (page 12 of Branch and Tree Decomposition Techniques for Discrete Optimization)

max degree 2

Suppose every factor has degree 2 and each variable is allowed to have its own range $d_i$

$$\sum_{v_1,v_2,v_3,v_4,v_5} f_1(v_1,v_2)f_2(v_3,v_4)f_3(v_4,v_5)f_4(v_5,v_1)=\text{tr}(ABCD)$$ enter image description here

Optimal elimination order can be found in $O(n \log n)$ time using algorithm by Hu/Shing: (wikipedia, Matrix Chain Multiplication and Polygon Triangulation Revisited and Generalized)

$\endgroup$
2

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.