Open access
Date
2015Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
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. Show more
Permanent link
https://doi.org/10.3929/ethz-a-010350411Publication status
publishedPublisher
ETH ZürichSubject
DATA COMMUNICATIONS (COMPUTER SYSTEMS); DATENKOMMUNIKATION (COMPUTERSYSTEME); PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEMEOrganisational unit
03950 - Hoefler, Torsten / Hoefler, Torsten
02150 - Dep. Informatik / Dep. of Computer Science
More
Show all metadata
ETH Bibliography
yes
Altmetrics