Faster Tensor Canonicalization

Abstract

The Butler-Portugal algorithm for obtaining the canonical form of a tensor expression with respect to slot symmetries and dummy-index renaming suffers, in certain cases with a high degree of symmetry, from $O(n!)$ explosion in both computation time and memory. We present a modified algorithm which alleviates this problem in the most common cases---tensor expressions with subsets of indices which are totally symmetric or totally antisymmetric---in polynomial time. We also present an implementation of the label-renaming mechanism which improves upon that of the original Butler-Portugal algorithm, thus providing a significant speed increase for the average case as well as the highly-symmetric special case. The worst-case behavior remains $O(n!)$, although it occurs in more limited situations unlikely to appear in actual computations. We comment on possible strategies to take if the nature of a computation should make these situations more likely.

45 pages + appendices and references, 9 figures, version 3 (fixed some references, grant acknowledgement, added link to source code)

References in corpus (3)

• xPerm: fast index canonicalization for tensor computer algebra
• A field-theory motivated approach to symbolic computer algebra
• The Invar tensor package: Differential invariants of Riemann

Cited by in corpus (2)

• LieART 2.0 -- A Mathematica Application for Lie Algebras and Representation Theory
• SeQuant Framework for Symbolic and Numerical Tensor Algebra. I. Core Capabilities