13.18.2 Tensor Contraction Cost Index Range

The Tensor Contraction Cost Index Range quantifies computational complexity in tensor operations, guiding efficient algorithm design within algebraic structures.

Tensor Contraction Cost Index Range is the specific span of values that a given index, whether free or contracted, is permitted to take, and the direct role that this span plays in determining how many terms must be summed or how many entries must be computed during a contraction, distinguishing the range associated with each individual index from the overall dimension of the space in cases where axes are not uniform.

Definition

Every index appearing in a tensor expression ranges over a specific set of values, most commonly:

i \in {1, 2, \dots, n_{i}}

where $n_{i}$ is the range size associated specifically with that index. The cost index range is this quantity $n_{i}$ , considered as a direct contributor to the total operation count of any contraction involving that index.

Range Versus Uniform Dimension

Uniform Case

When every axis of every tensor involved shares the same dimension $n$ , the cost index range coincides with the general cost dimension factor, and no distinction between individual index ranges is needed.

Non-Uniform Case

When different axes of a tensor, or different tensors in an expression, have different sizes, such as a tensor of shape $3 \times 7 \times 5$ , each index carries its own distinct cost index range, and the total cost of a contraction must be computed using the specific range of the index actually being contracted or retained, not an assumed common dimension.

cost of contracting index j = n_{j} \times (cost per term)

Role in Cost Formulas

Contracted Index Ranges

Each contracted index contributes its own range as a multiplicative factor in the summation cost, since the contraction must iterate once for every value in that specific index's range, independent of the ranges of any other index in the expression.

Free Index Ranges

Each surviving free index contributes its own range as a multiplicative factor in the size of the output array, since one output entry must be produced for every combination of values the free indices can jointly take.

Combined Formula

For an expression with free index ranges $n_{f 1}, \dots, n_{f r}$ and one contracted index of range $n_{c}$ , the total cost is:

cost = n_{f 1} \times \dots \times n_{f r} \times n_{c}

Diagram of Mixed Ranges

Practical Importance

Recognizing distinct cost index ranges is essential whenever the tensors involved in a contraction are not uniform in shape, since applying the cost dimension factor formula with a single assumed dimension in place of the true, individually varying ranges would produce an incorrect estimate of computational cost, potentially misidentifying which grouping or ordering of a contraction sequence is actually the cheapest to execute.