TY - JOUR

T1 - Fast bilinear algorithms for symmetric tensor contractions

AU - Solomonik, Edgar

AU - Demmel, James

N1 - Funding Information:
This work used the Extreme Science and Engineering Discovery Environment (XSEDE), which is supported by National Science Foundation grant number ACI-1548562. Via XSEDE, the authors made use of the TACC Stampede2 supercomputer.
Publisher Copyright:
© 2021 De Gruyter. All rights reserved.

PY - 2021/1/1

Y1 - 2021/1/1

N2 - In matrix-vector multiplication, matrix symmetry does not permit a straightforward reduction in computational cost. More generally, in contractions of symmetric tensors, the symmetries are not preserved in the usual algebraic form of contraction algorithms. We introduce an algorithm that reduces the bilinear complexity (number of computed elementwise products) for most types of symmetric tensor contractions. In particular, it lowers the bilinear complexity of symmetrized contractions of symmetric tensors of order s + v and v + t by a factor of (s+t+v)!/s!t!v! to leading order. The algorithm computes a symmetric tensor of bilinear products, then subtracts unwanted parts of its partial sums. Special cases of this algorithm provide improvements to the bilinear complexity of the multiplication of a symmetric matrix and a vector, the symmetrized vector outer product, and the symmetrized product of symmetric matrices. While the algorithm requires more additions for each elementwise product, the total number of operations is in some cases less than classical algorithms, for tensors of any size. We provide a round-off error analysis of the algorithm and demonstrate that the error is not too large in practice. Finally, we provide an optimized implementation for one variant of the symmetry-preserving algorithm, which achieves speedups of up to 4.58× for a particular tensor contraction, relative to a classical approach that casts the problem as a matrix-matrix multiplication.

AB - In matrix-vector multiplication, matrix symmetry does not permit a straightforward reduction in computational cost. More generally, in contractions of symmetric tensors, the symmetries are not preserved in the usual algebraic form of contraction algorithms. We introduce an algorithm that reduces the bilinear complexity (number of computed elementwise products) for most types of symmetric tensor contractions. In particular, it lowers the bilinear complexity of symmetrized contractions of symmetric tensors of order s + v and v + t by a factor of (s+t+v)!/s!t!v! to leading order. The algorithm computes a symmetric tensor of bilinear products, then subtracts unwanted parts of its partial sums. Special cases of this algorithm provide improvements to the bilinear complexity of the multiplication of a symmetric matrix and a vector, the symmetrized vector outer product, and the symmetrized product of symmetric matrices. While the algorithm requires more additions for each elementwise product, the total number of operations is in some cases less than classical algorithms, for tensors of any size. We provide a round-off error analysis of the algorithm and demonstrate that the error is not too large in practice. Finally, we provide an optimized implementation for one variant of the symmetry-preserving algorithm, which achieves speedups of up to 4.58× for a particular tensor contraction, relative to a classical approach that casts the problem as a matrix-matrix multiplication.

KW - Bilinear Complexity

KW - Symmetric Matrices

KW - Symmetric Tensors

KW - Tensor Contractions

UR - http://www.scopus.com/inward/record.url?scp=85079619179&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85079619179&partnerID=8YFLogxK

U2 - 10.1515/cmam-2019-0075

DO - 10.1515/cmam-2019-0075

M3 - Article

AN - SCOPUS:85079619179

VL - 21

SP - 211

EP - 231

JO - Computational Methods in Applied Mathematics

JF - Computational Methods in Applied Mathematics

SN - 1609-4840

IS - 1

ER -