Contracting Symmetric Tensors Using Fewer Multiplications

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.

Contracting symmetric tensors using fewer multiplicatio