13.17.4 Tensor Contraction Sequence Cost Effect

Tensor Contraction Sequence Cost Effect is the influence that the chosen order and grouping of a multi-step contraction sequence has on the total number of arithmetic operations required to compute the final residual tensor, even when different orderings are guaranteed by associativity context to yield the identical result.

Definition

For a sequence contracting tensors $$A,B,C$$ with respective dimensions along the contracted axes, the computational cost of a given grouping is measured by the total number of scalar multiplications needed to evaluate it. The cost effect is the observation that this total can differ substantially between mathematically equivalent groupings:

in general, even though both groupings compute the same tensor.

Source of the Cost Difference

Intermediate Array Size

Each grouping choice produces a different intermediate tensor at its first step, and the size of that intermediate array directly affects how many operations the second step requires. A grouping that produces a small intermediate tensor first is typically cheaper than one that produces a large intermediate tensor first.

Illustrative Dimension Count

For matrices of sizes $$m\times n$$, $$n\times p$$, and $$p\times q$$, contracted in a chain, the two possible groupings require:

which are generally unequal expressions in $$m,n,p,q$$, so one grouping can be far cheaper than the other depending on the relative sizes of these dimensions.

General Behavior Across Longer Sequences

Growth With Sequence Length

As the number of tensors contracted in a chain grows, the number of distinct valid groupings grows rapidly, and the gap in cost between the cheapest and most expensive grouping tends to widen, particularly when the tensors involved have widely varying dimensions.

Selection of a Minimal-Cost Grouping

Among all groupings that are equivalent under the associativity context, there generally exists one, or a small set of tied groupings, achieving the minimum total operation count. Identifying such a grouping is a distinct combinatorial question from establishing that the groupings are equal in value.

Cost Comparison Diagram

Relation to Associativity Context

The cost effect does not contradict the associativity context: both groupings remain mathematically identical in result, and the cost effect concerns only the practical computational resources required to reach that identical result, making the choice of grouping a matter of efficiency rather than correctness.