Tensor networks and contraction paths

Describe tensor networks with indices and dimensions, represent contraction order using trees and paths, and validate inputs and paths.

Representing a tensor network

A tensor network specifies which tensors to multiply and which indices to sum over. An index labels a tensor axis: matrix rows and columns are two axes, and the length of each axis is its dimension. For example, the product of three matrices can be written as

b and c are summed indices; a and d remain as the two result axes. ArcTN optimizes the contraction order from these connections and dimensions without reading tensor values.

Writing ArcTN inputs

Let $A$, $B$, and $C$ have shapes $2\times3$, $3\times4$, and $4\times5$:

inputs = [("a", "b"), ("b", "c"), ("c", "d")]
output = ("a", "d")
size_dict = {"a": 2, "b": 3, "c": 4, "d": 5}

• The outer order of inputs matches the input array order: A, B, C in this example, supplied as [A, B, C] at execution. Each tuple lists indices in array-axis order; for example, ("a", "b") assigns a to the rows and b to the columns of the first matrix. It does not specify a contraction order.
• output specifies the result axes. Here a labels the rows and d the columns, giving shape (2, 5).
• size_dict gives the dimension of each index. Matching labels refer to the same index, regardless of the names themselves.

The Python interface accepts hashable labels and converts them to integer IDs before entering Rust. With Quimb, pass ArcTNOptimizer directly and let Quimb supply the network information; see the Quimb example.

Edges, hyperedges, and output indices

An index connecting two distinct tensors can be drawn as an ordinary edge; one connecting three or more distinct tensors is a hyperedge. Indices not listed in output are eventually summed out, while output indices are retained.

Two axes of the same tensor may also share a label. If that index appears in neither other tensors nor the output, it is traced out, as in $\sum_i A_{ii}$. Otherwise, a diagonal is taken first, retaining one index for subsequent contraction.

The same index may appear at most twice in a single input tensor. Three or more occurrences cause network validation to fail.

Contraction trees and paths

The network defines the tensor expression to compute, but not which tensors to contract first. In the example above, either $AB$ or $BC$ can be computed first:

Both orders yield the same mathematical result, but differ in work and intermediate tensor sizes:

The largest contraction result includes the final output. Although the first path initially produces 8 elements, the final output still has 10.

The parenthesization corresponds to a binary contraction tree: leaves are inputs, internal nodes are binary contractions, and the root is the final result. A path lists these steps in execution order. Independent steps within the same tree may be reordered.

SSA paths: fixed tensor IDs

ArcTN internally uses static single assignment (SSA) paths. Each input and each step result has a fixed ID, and every new result receives a new ID. With n inputs, input IDs are 0..n-1; step s produces ID n+s, with s starting at 0. The two tensors consumed by a contraction cannot be used again, and the result uses its new ID.

Integers in a path refer to whole tensors. They are distinct from index labels such as "a" and "b" in inputs, which label tensor axes.

For the $A(BC)$ order in the three-tensor example:

Input IDs: A = 0, B = 1, C = 2
SSA path: [(1, 2), (0, 3)]

Step 0: contract B with C; assign result ID 3
Step 1: contract A with result 3; assign final result ID 4

Linear paths: positions in the current list

An opt_einsum linear path uses positions in the current tensor list. Each step removes its two input tensors and appends the result, changing later positions. After the first step above, [A, B, C] becomes [A, BC], so the second step uses (0, 1). The complete linear path is [(1, 2), (0, 1)].

from arctn import arctn_path

linear_path = arctn_path(inputs, output, size_dict)
ssa_path = arctn_path(inputs, output, size_dict, use_ssa=True)

SSA and linear paths are both lists of integer pairs, but their IDs mean different things. Specify the path format whenever saving or passing a path.

Comparing candidate contraction trees

The same tensor network admits different contraction trees. Search methods generate and improve candidates, then compare their complete-path objective values. The diagram below shows five parenthesizations of four inputs A, B, C, D:

Selecting by the objective

Let $\mathcal C$ be the complete candidate paths included in the final comparison of this search, and let $J(P)$ be the objective of path $P$. Select

$P^*$ is one of the candidates with the lowest objective. How FLOPs and read/write volume form $J(P)$ is explained in Path metrics and optimization objective.

The diagram compares unsliced paths. With slicing, comparison uses total work across all slices; dynamic slicing may also adjust the path. See Slicing principles.

What “best candidate” means

Light and Heavy return the best candidate found during the current search, without guaranteeing local or global optimality. simulate_path can independently validate a path.

Parallel search and random seeds

RAYON_NUM_THREADS sets the width of the Rayon thread pool used for search, and seed sets the base random seed for the call. Ordinary use needs just one Light or Heavy search. For the distinction between thread configuration and repeated measurements, see Using Heavy and Single-machine parallelism.

Input validation

Input validation first checks that the network is fully defined: at least one input tensor, positive integer dimensions for all indices, and unique output indices drawn from the inputs. size_dict must not contain unused entries. For example, omitting "b": 3 above leaves the dimension connecting A and B undefined.

Execution also checks array counts and shapes. For example, inputs[0] = ("a", "b"), size_dict["a"] = 2, and size_dict["b"] = 3 require the first array to have shape (2, 3). A dimension mismatch or a tensor element count beyond the platform-representable range causes an error.

When constructing TensorNetwork directly through Rust struct fields, call validate() explicitly.

Path validation

simulate_path checks each SSA step and computes PathStats. It processes only network structure and dimensions, without contracting actual arrays. See Path metrics and optimization objective for metric definitions and examples.

Each step must reference two different, still-available tensor IDs. Exactly one result must remain at the end, with indices matching output. A single-tensor network may use an empty path; required summation, traces, or diagonals are handled by unary operations. See Validating inputs and handling errors.