Methods and systems for tensor network contraction based on local optimization of contraction tree

1 . A method implemented by a computing host, the method comprising:

obtaining a contraction tree associated with a tensor network, wherein a plurality of vertices and edges of the contraction tree correspond to a set of tensor nodes and indices of the tensor network respectively, the obtaining the contraction tree associated with the tensor network including decomposing the tensor network into two or more sub-graphs with a minimum count of edges that connect different sub-graphs such that a number of edges across the sub-graphs is minimum;

iteratively performing operations until a termination condition is satisfied, the termination condition including a storage cost of the contraction tree being less than a preset threshold, the storage cost including a memory size required to store a new tensor generated during a contraction of two tensors in the contraction tree, the operations including:

selecting a sub-graph of the contraction tree;

performing a top-layer hypergraph decomposition using a multi-partite decomposition algorithm with a first set of parameters;

performing subsequent layers decompositions using a bipartition decomposition algorithm with a second set of parameters;

dynamically adjusting the first set of parameters and the second set of parameters;

generating a local optimal sub-graph that has the storage cost less than the preset threshold;

replacing the sub-graph with the local optimal sub-graph; and

obtaining an optimized contraction tree including the local optimal sub-graph; and

outputting the optimized contraction tree.

2 . The method of claim 1 , wherein the generating the local optimal sub-graph that has the storage cost less than the preset threshold comprises:

reconstructing the sub-graph;

computing a contraction cost of a reconstructed sub-graph;

determining that the contraction cost of the reconstructed sub-graph is less than a contraction cost preset threshold; and

setting the reconstructed sub-graph as the local optimal sub-graph.

3 . The method of claim 2 , wherein the contraction cost of the reconstructed sub-graph is determined based at least in part on a number of nodes in the reconstructed sub-graph and the indices associated with the number of nodes.

4 . The method of claim 2 , wherein the contraction cost of the reconstructed sub-graph includes at least one of a computation cost or a storage cost.

5 . The method of claim 1 , wherein the termination condition further includes at least one of a number of reconstruction iterations, an individual contraction cost of the sub-graph, or a total contraction cost of the contraction tree.

6 . The method of claim 5 , wherein the total contraction cost of the contraction tree is determined based on the individual contraction cost associated with the sub-graph, the individual contraction cost indicating a complexity degree of a contraction computation.

7 . The method of claim 6 , wherein the complexity degree of the contraction computation includes at least one of a temporal complexity degree or a spatial complexity degree.

8 . The method of claim 5 , the termination condition being met indicates at least one of the number of reconstruction iterations satisfies a preset threshold, or the total contraction cost of the contraction tree is less than a preset bound.

9 . The method of claim 1 , wherein the sub-graph is a randomly selected connected sub-graph.

10 . A system comprising:

one or more processors, and

memory communicatively coupled to the one or more processors, the memory storing computer-executable modules executable by the one or more processors that, when executed by the one or more processors, perform actions including:

obtaining a contraction tree associated with a tensor network, wherein a plurality of vertices and edges of the contraction tree correspond to a set of tensor nodes and indices of the tensor network respectively, the obtaining the contraction tree associated with the tensor network including decomposing the tensor network into two or more sub-graphs with a minimum count of edges that connect different sub-graphs such that a number of edges across the sub-graphs is minimum;

iteratively performing operations until a termination condition is satisfied, the termination condition including a storage cost of the contraction tree being less than a preset threshold, the storage cost including a memory size required to store a new tensor generated during a contraction of two tensors in the contraction tree, the operations including:

selecting a sub-graph of the contraction tree;

performing a top-layer hypergraph decomposition using a multi-partite decomposition algorithm with a first set of parameters;

performing subsequent layers decompositions using a bipartition decomposition algorithm with a second set of parameters;

dynamically adjusting the first set of parameters and the second set of parameters;

generating a local optimal sub-graph that has the storage cost less than the preset threshold;

replacing the sub-graph with the local optimal sub-graph; and

obtaining an optimized contraction tree including the local optimal sub-graph; and

outputting the optimized contraction tree.

11 . The system of claim 10 , wherein the generating the local optimal sub-graph that has the storage cost less than the preset threshold comprises:

reconstructing the sub-graph;

computing a contraction cost of a reconstructed sub-graph;

determining that the contraction cost of the reconstructed sub-graph is less than a contraction cost preset threshold; and

setting the reconstructed sub-graph as the local optimal sub-graph.

12 . The system of claim 11 , wherein the contraction cost of the reconstructed sub-graph includes at least one of a computation cost or a storage cost.

13 . The system of claim 10 , wherein the termination condition further includes at least one of a number of reconstruction iterations, an individual contraction cost of the sub-graph, or a total contraction cost of the contraction tree.

14 . The system of claim 13 , wherein the total contraction cost of the contraction tree is determined based on the individual contraction cost associated with the sub-graph, the individual contraction cost indicating a complexity degree of a contraction computation.

15 . The system of claim 13 , the termination condition being met indicates at least one of the number of reconstruction iterations satisfies a preset threshold, or the total contraction cost of the contraction tree is less than a preset bound.

16 . The system of claim 10 , wherein the sub-graph is a randomly selected connected sub-graph.

17 . A computer-readable storage medium storing computer-readable instructions executable by one or more processors of a video compression system, that when executed by the one or more processors, cause the one or more processors to perform actions comprising:

obtaining a contraction tree associated with a tensor network, wherein a plurality of vertices and edges of the contraction tree correspond to a set of tensor nodes and indices of the tensor network, respectively;

iteratively performing operations until a termination condition is satisfied, the termination condition including a computation cost of the contraction tree being less than a first preset threshold and a storage cost of the contraction tree being less than a second preset threshold, the computation cost including a number of dot multiplications to be performed in a contraction of two tensors in the contraction tree, the storage cost including a memory size required to store a new tensor generated during the contraction, dimensions of respective indices of the two tensors being same, the operations including:

selecting a sub-graph of the contraction tree;

performing a top-layer hypergraph decomposition using a multi-partite decomposition algorithm with a first set of parameters;

performing subsequent layers decompositions using a bipartition decomposition algorithm with a second set of parameters;

dynamically adjusting the first set of parameters and the second set of parameters;

generating a local optimal sub-graph that has the computation cost less than the first preset threshold or the storage cost less than the second preset threshold;

replacing the sub-graph with the local optimal sub-graph; and

obtaining an optimized contraction tree including the local optimal sub-graph;

in response to determining that more than one optimized contraction trees meet the termination condition, selecting a contraction tree with a minimum computation cost or a minimum storage cost as an optimal contraction tree; and

outputting the optimal contraction tree.

18 . The computer-readable storage medium of claim 17 , wherein the generating the local optimal sub-graph that has the computation cost less than the first preset threshold or the storage cost less than the second preset threshold comprises:

reconstructing the sub-graph;

computing a contraction cost of a reconstructed sub-graph;

determining that the contraction cost of the reconstructed sub-graph is less than a contraction cost preset threshold; and

setting the reconstructed sub-graph as the local optimal sub-graph.

19 . The computer-readable storage medium of claim 18 , wherein the contraction cost of the reconstructed sub-graph includes at least one of a computation cost of the reconstructed sub-graph or a storage cost of the reconstructed sub-graph.

20 . The computer-readable storage medium of claim 17 , wherein the termination condition further includes at least one of a number of reconstruction iterations, or an individual contraction cost of the sub-graph.