13.18 Tensor Contraction Cost Analysis

Tensor Contraction Cost Analysis is the systematic study of how many arithmetic operations are required to evaluate a tensor contraction or a sequence of contractions, examining how the tensor orders, the dimension of the underlying vector space, and the grouping of steps together determine the total computational burden of carrying the operation out.

Definition

Cost analysis assigns to a contraction, or a sequence of contractions, a numerical estimate of computational work, typically counted in scalar multiplications, expressed as a function of the relevant tensor dimensions:

where each $$n_i$$ denotes the size of one of the axes involved, whether free or contracted, in the expression under analysis.

Components of a Cost Analysis

Single Contraction Cost

For one contraction over a shared axis of dimension $$n$$, cost analysis quantifies the operation count as directly proportional to $$n$$, the cost dimension factor, together with the product of the dimensions of all remaining free axes.

Sequence Cost

For a chain of several contractions, cost analysis accounts for the size of each intermediate tensor produced along the way, since the cost of each subsequent step depends on the size of the tensor it operates on, not merely on the original input sizes.

Grouping Sensitivity

Cost analysis reveals that mathematically equivalent groupings of the same contraction sequence, guaranteed identical in result by result preservation, can differ substantially in total operation count, motivating the search for a grouping of minimal cost as a distinct optimization question from correctness.

Typical Cost Analysis Procedure

Step One: Enumerate Dimensions

List the dimension of every axis appearing in the expression, distinguishing free axes that survive to the final result from contracted axes that are summed away.

Step Two: Identify Contraction Order

Determine the sequence in which contractions will be carried out, noting which intermediate tensors are formed at each stage.

Step Three: Sum Per-Step Costs

Compute the operation count for each individual step using its own input and output dimensions, then sum these counts across the entire sequence to obtain the total cost:

Step Four: Compare Alternatives

Repeat the above steps for each candidate grouping or ordering under consideration, and compare the resulting totals to identify the most economical strategy.

Diagram of a Cost Analysis Workflow

Purpose Within the Broader Study of Contractions

Cost analysis provides the quantitative foundation underlying practical decisions about how to carry out large tensor computations, connecting the abstract guarantees of associativity and result preservation, which establish that many execution strategies are mathematically valid, with the concrete question of which among those valid strategies is computationally preferable given the specific dimensions involved.