Tensor networks and contraction complexity

Suppose two real tensors share indices of combined size k, while their remaining indices have combined sizes m and n. After consistent reshaping, contracting all the shared indices is multiplication of an m-by-k matrix by a k-by-n matrix. The elementary dense algorithm uses mkn scalar multiplications and mn(k − 1) additions. When k is large, a common leading floating-point count is approximately 2mkn, but that convention counts both operation types.

The output contains mn entries, independently of how many arithmetic operations were required. Its storage is only one part of memory use: existing inputs, workspace, and other live intermediates also matter. These counts assume dense arrays and the classical multiplication algorithm; sparsity, symmetry, low-rank blocks, or faster matrix multiplication may change them. Comparing plans is meaningful only under a shared cost model.

Consider a network region already contracted into one intermediate tensor. Its remaining indices are exactly the edges crossing the region’s boundary, together with requested physical output indices. If every such index has dimension χ and there are w of them, the dense intermediate has χʷ entries. For unequal dimensions, replace that power by the product of boundary dimensions. The sequence of boundaries induced by an ordering controls its memory growth.

This explains why tree-like or narrow-width structures can be tractable when bond dimensions stay bounded, whereas a poor ordering can expose a large boundary. Graph-width methods formalize the relation between network geometry and contraction complexity, with precise graph and dimension conventions. We use the boundary-product count directly rather than asserting that the number of local tensors alone determines the cost. Even a short matrix chain already exhibits a substantial ordering effect.

A tensor train with bounded ranks can evaluate one entry by multiplying its selected core slices without forming the full tensor. Contracting an inner product of two trains also benefits from a structured sequence of small environments. But requesting every dense entry still has a product-of-mode-sizes output cost. A compact representation removes unnecessary materialization only when the requested computation can exploit that representation.

Replacing an intermediate with a low-rank approximation can further reduce computation, but it changes the result and needs an error budget. Exact reordering changes only evaluation order, apart from floating-point rounding; truncation introduces approximation error as well. Finally, fewer arithmetic operations need not translate proportionally into wall-clock speed because memory traffic, parallelism, and kernel sizes matter. Operation counts and roofline ceilings inform different parts of that performance assessment.