Contractions of nonsymmetric tensors are reducible to matrix

multiplication, however, ‘fully symmetric contractions’ in which the

tensors are symmetric and the result is symmetrized can be done

with fewer operations. The ‘direct evaluation algorithm’ for fully

symmetric contractions exploits equivalence between terms in the

contraction equation to obtain a lower computation cost than the

cost associated with nonsymmetric contractions. The ‘symmetry

preserving algorithm’ lowers the cost even further via an algebraic

reorganization of the contraction equation. We derive vertical

(between memory and cache) and horizontal (interprocessor)

communication lower bounds for both of these algorithms.

We demonstrate that any load balanced parallel schedule of the direct

evaluation algorithm requires asymptotically more horizontal

communication for some fully symmetric contractions than matrix

multiplication for nonsymmetric contractions of the same size. Instances

of such fully symmetric contractions arise in quantum chemistry

calculations. Further, we prove that any schedule of the symmetry

preserving algorithm requires asymptotically more vertical and

horizontal communication than the direct evaluation algorithm for

some fully symmetric contractions. However, for the instances of

fully symmetric contractions that arise in quantum chemistry

calculations, our lower bounds are asymptotically the same for both

of these algorithms.

Communication lower bounds for tensor contraction algorithms