Mathematically, symmetry is a free lunch. If a high-order tensor is symmetric—meaning its entries are invariant under any permutation of their indices—we can theoretically discard redundant data. For a $d$-order tensor, we only need to store the unique entries in the upper hypertriangular region, reducing the memory footprint and the number of theoretical arithmetic operations by a factor of roughly $d!$.
In practice, however, modern computing architectures do not operate on pure mathematics; they operate on memory hierarchies and communication networks. Translating structural symmetry into hardware efficiency reveals a profound trade-off: minimizing storage and arithmetic often severely degrades data locality and increases data movement (communication) across parallel processors.
The Administrative Cost of Packed Storage
The most immediate challenge of exploiting symmetry is memory layout. Computers achieve peak performance when accessing contiguous, predictable blocks of memory. When a symmetric tensor is compressed into a "packed" format to store only unique elements, this regular linear indexing is shattered.
Andreas Griewank et al. documented this friction when evaluating higher derivative tensors. They found that the administrative overhead required to manage symmetric tensor storage frequently eclipsed the theoretical benefits of saving space. Calculating the non-contiguous memory addresses for unique entries introduces complex, irregular indexing logic. This addressing overhead often negates the advantages of a reduced data volume by disrupting the contiguous memory access patterns that hardware prefetchers rely on.
To mitigate this, Martin D. Schatz et al. proposed a blocked storage data structure that partitions symmetric tensors into blocks, saving only unique blocks within an upper hypertriangular region and using metadata to reconstruct the full tensor. While this helps bridge the gap for high-performance libraries, the fundamental tension remains: squeezing out redundant entries complicates memory access, creating a persistent bottleneck in execution time.
Why Symmetry Increases Communication Overhead
In modern high-performance computing, data movement—rather than arithmetic computation—is the primary bottleneck. Algorithms must maximize data reuse (keeping data in fast local cache or minimizing transfers between parallel nodes) to run efficiently.
Standard tensor contractions are typically mapped to optimized matrix multiplication routines, which rely on regular, blockable data structures. Slicing matrices into uniform blocks allows processors to compute independently and reuse data heavily within local memory. However, algebraically reorganizing a contraction to exploit symmetry disrupts this blockable structure.
As Edgar Solomonik et al. demonstrated, minimizing multiplications via algebraic identities fractures spatial and temporal data locality. Because the unique elements needed for a computation are scattered across index permutations, the hardware cannot effectively reuse data within fast cache memory, forcing frequent and costly transfers from slower main memory.
This issue compounds in distributed-memory parallel environments. Packed storage formats prevent the clean, independent data partitioning required for optimal communication between processors. Edgar Solomonik et al. proved that for certain tensor contraction configurations, packed storage layouts force asymptotically higher "horizontal" communication across parallel processors compared to standard unpacked layouts. For instance, in matrix-vector-like contractions, packed storage can degrade horizontal communication scaling from an unpacked rate of $\Omega(n^2/p)$ to a significantly more expensive rate of $\Omega(n^2/p^{2/3})$, where $p$ is the number of processors.
Because data movement is so costly, the authors show that when extra memory is available, it is often asymptotically faster to explicitly unpack a symmetric tensor. Prioritizing communication efficiency over a minimal memory footprint allows the system to leverage standard, highly optimized parallel matrix operations.
Algorithmic Workarounds: Implicit Construction and Sketching
Faced with this trade-off, researchers have developed specialized algorithmic strategies to handle massive symmetric tensors without suffering catastrophic memory or communication failures.
One strategy is to avoid explicit matrix formation entirely during optimization. In the context of tensor decompositions, Kim Batselier et al. introduced an iterative algorithm (STEROID) that computes the normal equations for least-squares refinement by exploiting structural symmetries implicitly. This allows the decomposition of high-order tensors that would otherwise trigger memory exhaustion. However, the authors noted a numerical trade-off: avoiding explicit matrix formation can square the condition number of the system, potentially reducing precision in poorly conditioned cases.
Another approach involves randomized dimensionality reduction, or sketching. When compressing massive datasets, general-purpose sketching algorithms often fail to recognize internal symmetry. As Yining Wang et al. pointed out, ignoring this symmetry leads to redundant hash operations and unnecessary processing time. Efficiently scaling these methods requires specialized sketching mechanisms designed to capture symmetric properties natively, bypassing redundant computations without destroying the underlying data structure.
The Matrix Exception: Increased Operational Intensity
Interestingly, the severe communication penalties associated with symmetry in high-order tensor contractions do not always apply to lower-dimensional matrix operations.
For core symmetric linear algebra kernels—such as Cholesky factorization and Symmetric Rank-k updates (SYRK)—input symmetry can actually be leveraged to reduce data movement. Olivier Beaumont et al. established new I/O lower bounds proving that exploiting symmetry in these matrix operations allows a single data element loaded into fast memory to serve multiple roles simultaneously. This increases the kernel's operational intensity, enabling a theoretical reduction in data movement by a factor of $\sqrt{2}$ compared to general, non-symmetric matrix multiplication.
The contrast between matrix kernels and tensor contractions highlights the nuance of the symmetry-communication trade-off. In two dimensions, data layouts remain regular enough that symmetry can enhance data reuse. But as we move to higher-order tensors, the permutations span multiple dimensions, fracturing data locality and forcing a stark algorithmic choice: conserve memory at the expense of communication, or waste memory to achieve speed.
Key Foundational Work
Exploiting Symmetry in Tensors for High Performance: Multiplication with Symmetric Tensors (2014) — contributed 11 concept elements to this direction.
Evaluating higher derivative tensors by forward propagation of univariate Taylor series (2000) — contributed 2 concept elements to this direction.
Symmetric Tensor Decomposition by an Iterative Eigendecomposition Algorithm (2014) — contributed 2 concept elements to this direction.