13.18.1 Tensor Contraction Cost Dimension Factor

Tensor Contraction Cost Dimension Factor is the multiplicative role that the dimension of the underlying vector space plays in determining the number of arithmetic operations required to evaluate a tensor contraction, isolating the specific contribution of the space's dimensionality from other factors such as tensor order or the number of contraction steps.

Definition

For a single contraction summing over an index ranging across an $$n$$-dimensional space, the cost dimension factor is the quantity $$n$$ itself, appearing directly as a linear multiplier in the total operation count:

Each additional unit of dimension adds exactly one more term to every summation performed during the contraction.

How the Factor Enters the Total Cost

Single Contraction of Two Matrices

For a matrix product contracting an $$m\times n$$ tensor against an $$n\times p$$ tensor over the shared dimension $$n$$, the total multiplication count is:

Here $$n$$ is the dimension factor associated specifically with the contracted axis, while $$m$$ and $$p$$ reflect the sizes of the surviving free indices.

Higher-Order Tensors

For a tensor of order $$r$$ with every axis of dimension $$n$$, contracting over one axis pair costs on the order of:

operations, since the remaining $$r-2$$ free indices each range over $$n$$ values and the contracted sum itself contributes one further factor of $$n$$.

Sensitivity to Dimension Growth

Polynomial Scaling

The cost dimension factor causes contraction cost to scale polynomially in $$n$$, with the degree of the polynomial determined by how many free and contracted indices are involved. Doubling the dimension of the space can multiply the total cost by a factor of $$2^k$$ for an expression involving $$k$$ total index positions.

Dominant Factor in Large Spaces

When the underlying space has large dimension, the cost dimension factor typically dominates the total computational cost of a contraction sequence far more than the number of contraction steps or the specific grouping chosen, making dimension reduction, where applicable, a more effective cost-saving strategy than reordering alone.

Visualizing the Growth

Relation to Overall Sequence Cost

The cost dimension factor combines multiplicatively with the number of free indices and, across a multi-step sequence, with the sizes of every intermediate tensor produced along the way, meaning that the sequence cost effect and the cost dimension factor jointly determine the total computational burden of a contraction sequence: grouping choice affects which intermediate sizes arise, while the dimension factor determines how expensive each individual summation is once that structure is fixed.