  Symmetric and sparse tensors arise naturally in many domains including linear
algebra, statistics, physics, chemistry, and graph theory. Symmetric tensors
are equal to their transposes, so in the $n$-dimensional case we can save up to
a factor of $n!$ by avoiding redundant operations. Sparse tensors, on the other
hand, are mostly zero, and we can save asymptotically by processing only
nonzeros. Unfortunately, specializing for both symmetry and sparsity at the
same time is uniquely challenging. Optimizing for symmetry requires
consideration of $n!$ transpositions of a triangular kernel, which can be
complex and error prone. Considering multiple transposed iteration orders and
triangular loop bounds also complicates iteration through intricate sparse
tensor formats. Additionally, since each combination of symmetry and sparse
tensor formats requires a specialized implementation, this leads to a
combinatorial number of cases. A compiler is needed, but existing compilers
cannot take advantage of both symmetry and sparsity within the same kernel. In
this paper, we describe the first compiler which can automatically generate
symmetry-aware code for sparse or structured tensor kernels. We introduce a
taxonomy for symmetry in tensor kernels, and show how to target each kind of
symmetry. Our implementation demonstrates significant speedups ranging from
1.36x for SSYMV to 30.4x for a 5-dimensional MTTKRP over the non-symmetric
state of the art.
