13.2.6 Tensor Contraction Cost Area

Tensor Contraction Cost Area measures computational expense in tensor operations, crucial for optimizing performance in algebraic calculations.

Tensor Contraction Cost Area is the domain within tensor contraction areas concerned with the number of arithmetic operations required to carry out a contraction, examining how the dimension of the contracted index and the number of free indices remaining jointly determine the computational effort needed to produce a result.

The Basis of Computational Cost

Counting Operations in a Single Summation

The cost of contracting a single pair of indices is governed by the number of terms summed, which equals the dimension of the space over which the contracted index ranges, since the summation convention requires evaluating and adding one term for every value that shared index can take.

T_{i}^{i} = \sum_{i = 1}^{n} T_{i}^{i}

Scaling with Free Indices

When free indices remain in the result, the summation defining the contracted index must be repeated once for every combination of values the free indices can take, so the total cost scales with the product of the dimension raised to the power of the number of free indices and the dimension of the contracted index itself.

cost \propto n^{f + 1}

Here $n$ denotes the common dimension involved and $f$ denotes the number of free indices remaining in the result.

Cost Considerations for Multiple Contractions

Additional Cost from Each Independent Pairing

Each additional independent contraction within an expression introduces its own summation over its own dimension, so that the overall cost of an expression containing several contractions reflects the combined effect of every summation, applied across every combination of the surviving free indices.

Cost Dependence on the Order of Contraction

When an expression permits contracting several index pairs in different possible sequences, the total number of arithmetic operations required can differ depending on which pairing is performed first, since an earlier contraction may reduce the size of intermediate results that later contractions must then process.

Cost in the Context of a Product Followed by Contraction

Avoiding Full Construction of the Product

Contracting an index immediately after forming a tensor product can be computed without ever fully constructing every component of the intermediate product, since only the components needed for the specific contracted pairing must be computed and summed, reducing cost relative to a naive two-step approach.

w^{i} = A_{j}^{i} v^{j}

Comparison Across Different Contraction Sequences

When more than one contraction remains to be performed across a chain of tensors, the total cost can vary substantially depending on which contraction in the chain is carried out first, motivating a comparison of the possible sequences before performing the computation.

Cost as Distinct from Correctness

Cost Independent of Verification Outcome

The computational cost of a contraction is a property of how the summation is carried out and does not affect whether the resulting tensor satisfies the structural and invariance requirements examined during verification, so a costly computation and an inexpensive one can both produce equally valid results.

Relevance Limited to Practical Computation

Tensor contraction cost area addresses concerns that arise specifically when contractions must actually be evaluated numerically, and does not bear on the purely algebraic questions of whether a contraction is defined or what tensor it produces, which are addressed by the structural and scope-related areas of contraction.

Relationship to Tensor Operation Notation

Tensor operation notation itself does not encode computational cost directly, but the number of distinct repeated index symbols and the dimension associated with each index, both of which are read from the notation, together determine the cost of evaluating the summations that the notation specifies.