13.18.4 Tensor Contraction Cost Ordering Effect

Tensor Contraction Cost Ordering Effect is the influence that the specific sequence in which independent contractions within a larger tensor network are carried out has on the total computational cost, viewed as a choice among the many valid execution orders permitted by result preservation, each of which routes the computation through a different set of intermediate tensors.

Definition

Given a network of several tensors linked by multiple contractions, an ordering is a specific sequence $$C_{\sigma },\dots ,C_{\sigma }$$ in which the required contractions are performed, for some permutation $$\sigma$$ of the available steps. The cost ordering effect is the observation that:

in general, for two distinct valid orderings $$\sigma$$ and $${\sigma }^{\prime }$$, even though both produce the identical final tensor by result preservation.

Mechanism of the Effect

Path Through Intermediate Sizes

Each ordering determines a distinct path through a sequence of intermediate tensors, and each such path has its own profile of intermediate sizes. Since per-step cost is proportional to the size of the intermediate tensor being processed, orderings that route through smaller intermediates at every stage tend to achieve lower total cost.

Interaction With Network Topology

In a network where several tensors share contracted indices with several others, the number of distinct valid orderings can be large, and the cost ordering effect becomes more pronounced as the network grows, since the disparity between the cheapest and most expensive valid ordering tends to widen with the number of tensors involved.

Contrast With Grouping

Distinction From Pure Grouping

Cost ordering effect specifically addresses the sequence in which distinct, already-identified contraction steps are executed, whereas grouping addresses how a chain of contractions is parenthesized. In a network with more than three tensors and multiple independent contraction pairs, ordering and grouping decisions can be intertwined, since a chosen order implicitly determines a corresponding nesting of intermediate products.

Search for a Minimal Ordering

Determining the ordering of least cost across a network with many tensors is a combinatorial search problem: the number of candidate orderings grows rapidly with the number of contractions, so identifying the cheapest ordering generally requires an explicit search or heuristic rather than direct inspection.

Illustration

Relevance to Cost Analysis

The cost ordering effect is one of the central quantities a full cost analysis must account for when evaluating a tensor network: alongside the cost dimension factor for each axis and the intermediate sizes produced along any given path, the choice of ordering determines exactly which path through the space of intermediate tensors the computation follows, and therefore which specific total cost is realized among the many values permitted by the network's topology.