We present more computationally-efficient algorithms for contracting symmetric tensors.
Tensor contractions are reducible to matrix multiplication, but permutational symmetries
of the data, which are expressed by the tensor representation, provide an opportunity
for more efficient algorithms. Previously known methods have exploited only tensor
symmetries that yield identical computations that are directly evident in the contraction
expression. We present a new ‘symmetry preserving’ algorithm that uses an algebraic
reorganization in order to exploit considerably more symmetry in the computation of the
contraction than the conventional approach. The new algorithm requires fewer multiplications
but more additions per multiplication than previous approaches. The applications of this
result include the capability to multiply a symmetric matrix by a vector, as well as compute
the rank-2 symmetric vector outer product in half the number of scalar multiplications,
albeit with more additions. The symmetry preserving algorithm can also be adapted to
perform the complex versions of these operations, namely the product of a Hermitian matrix
and a vector and the rank-2 Hermitian vector outer product, in 3/4 of the overall
operations. Consequently, the number of operations needed for the direct algorithm to
compute the eigenvalues of a Hermitian matrix is reduced by the same factor.
Our symmetry preserving tensor contraction algorithm can also be adapted to the
antisymmetric case and is therefore applicable to the tensor-contraction computations
employed in quantum chemistry. For these applications, notably the coupled-cluster method,
our algorithm yields the highest potential speed-ups, since in many higher-order contractions
the reduction in the number of multiplications achieved by our algorithm enables an equivalent
reduction in overall contraction cost. We highlight that for three typical coupled-cluster contractions
taken from methods of three different orders, our algorithm achieves 2X, 4X, and 9X improvements
in arithmetic cost over the standard approach.