论文标题
在树木张量网络的最佳线性收缩顺序上，
On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
论文作者
论文摘要
张量网络的收缩成本取决于收缩顺序。但是，已知最佳的收缩排序问题是NP-HARD。我们表明，通过将连接连接到数据库联接顺序，树木张量网络的线性收缩排序问题接受了多项式时间算法。结果依赖于收缩成本的相邻序列互换属性，该属性可以基于局部比较对收缩顺序进行全局决策。基于此，我们指定了IKKBZ数据库的修改版本JOIN ORDERING算法，以找到最佳的树张量网络线性收缩顺序。最后，我们将算法扩展到一般收缩顺序和任意张量网络拓扑的启发式启发式。
The contraction cost of a tensor network depends on the contraction order. However, the optimal contraction ordering problem is known to be NP-hard. We show that the linear contraction ordering problem for tree tensor networks admits a polynomial-time algorithm, by drawing connections to database join ordering. The result relies on the adjacent sequence interchange property of the contraction cost, which enables a global decision of the contraction order based on local comparisons. Based on that, we specify a modified version of the IKKBZ database join ordering algorithm to find the optimal tree tensor network linear contraction order. Finally, we extend our algorithm as a heuristic to general contraction orders and arbitrary tensor network topologies.
