Hypergraph bisection

Build a contraction tree by recursively partitioning the tensor hypergraph, using dynamic programming for small subproblems.

Building a contraction tree by partitioning

Hypergraph bisection treats tensors as vertices and shared indices as hyperedges connecting the corresponding vertices. It partitions the vertices into two groups, processes each recursively, then contracts the two results.

An ordinary edge connects two vertices; a hyperedge may connect more than two. If one index occurs in three tensors, a single hyperedge connects all three. The partition determines which tensors are contracted within each group before the two groups are combined.

Subject to group-size constraints, the partition aims to minimize the weighted sum of hyperedges crossing between groups:

$d_e$ is the dimension of the corresponding index. This partition cost is not the FLOPs or memory traffic of the complete path. Partitioning only determines the contraction tree; it neither removes indices nor performs slicing.

Recursive process

First partition a smaller hypergraph formed by coarsening vertices, then expand and refine the partition level by level. Repeat on each side; when the vertex count is at most cutoff, switch to subset dynamic programming.

Build subtree(S):
    if S contains only one tensor:
        return that tensor
    if the number of tensors in S <= cutoff:
        return the local tree found by subset DP
    (L, R) = bisect hypergraph S
    left = build subtree(L)
    right = build subtree(R)
    return the tree obtained by merging left and right

Different random seeds and balance parameters produce different candidates. After multiple trials, choose by the objective value of the complete path. Process disconnected components separately, then combine them by outer product in size order.

Interfaces

bisect uses the default objective; bisect_with_objective lets you specify the objective used to compare complete candidates. For small subproblems, optimal_dp still uses the default objective $F+64R$, not the caller-supplied weights. cutoff must be between 2 and 20; see the signatures in the Rust API.

Bisection is a heuristic and does not guarantee a globally optimal path. Light uses bisection candidates; Heavy does not. See Light / Heavy interfaces.