xPerm: fast index canonicalization for tensor computer algebra

2008/03/06 by José M. Martín-García, Jose M. Martin-Garcia · 222 citations
Computer Science · Mathematics · Physics and Astronomy · #Algebra over a field #Algorithm #Byte #Computer science #Geometry #Identifier #Linear algebra #Mathematics #Matrix Theory and Algorithms #Permutation (music) #Polynomial #Programming language #Pulsars and Gravitational Waves Research #Pure mathematics #Software #Subalgebra #Subroutine #Symbolic computation #Tensor (intrinsic definition) #Tensor algebra #Tensor decomposition and applications #Unix #cs.SC #gr-qc #hep-th

paper · pdf · doi:10.1016/j.cpc.2008.05.009

published in Computer Physics Communications 179(8), 597-603 (Elsevier BV) · 16 pages, 3 figures. Package can be downloaded from http://metric.iem.csic.es/Martin-Garcia/xAct/

arxiv created 2008/03/06 · openalex publication_date 2008/06/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We present a very fast implementation of the Butler-Portugal algorithm for index canonicalization with respect to permutation symmetries. It is called xPerm, and has been written as a combination of a Mathematica package and a C subroutine. The latter performs the most demanding parts of the computations and can be linked from any other program or computer algebra system. We demonstrate with tests and timings the effectively polynomial performance of the Butler-Portugal algorithm with respect to the number of indices, though we also show a case in which it is exponential. Our implementation handles generic tensorial expressions with several dozen indices in hundredths of a second, or one hundred indices in a few seconds, clearly outperforming all other current canonicalizers. The code has been already under intensive testing for several years and has been essential in recent investigations in large-scale tensor computer algebra.

Citations

• The Invar tensor package

Cited by

• Approximate helical symmetry in compact binaries
• Conformally Invariant Corrections to the Anomaly-Induced Effective Action and Black Hole Evaporation in Four Dimensions
• Cancellation of UV divergences in ghost-free infinite derivative gravity
• Sound as a gauge theory and its infrared triangle
• Weak Gravity Conjecture in the sky: gravitational waves from preheating in Einstein-Maxwell-Scalar EFT
• FieldsX -- An extension package for the xAct tensor computer algebra suite to include fermions, gauge fields and BRST cohomology
• SeQuant Framework for Symbolic and Numerical Tensor Algebra. I. Core Capabilities
• Generalized Effective Field Theory for Four-Dimensional Black Hole Evaporation
• Towards theory constraints on ultralight dark matter from quantum gravity
• Yukawa interactions in Quantum Gravity
• On the uniqueness of higher-spin symmetries in AdS and CFT
• Local Expansion Mechanisms for Quantum-Scale Wormholes
• Covariant Galileon
• Form Factors in Asymptotic Safety: conceptual ideas and computational toolbox
• Matter Spectral Functions from Quantum Gravity
• Introduction to Redberry: a computer algebra system designed for tensor manipulation
• Gravitational waves from b-EMRIs: Doppler shift and beaming, resonant excitation, helicity oscillations and self-lensing
• F-theory Vacua and α'-Corrections
• Essential Renormalization Group Equation for Gravity coupled to a Scalar field
• Effective Field Theory Description of Hawking Radiation
• Canonical formulation of gravitating spinning objects at 3.5 post-Newtonian order
• Reformulations of Yang–Mills theories with space–time tensor fields
• Motion and gravitational wave forms of eccentric compact binaries with orbital-angular-momentum-aligned spins under next-to-leading order in spin–orbit and leading order in spin(1)–spin(2) and spin-squared couplings
• Next-to-next-to-leading order post-Newtonian spin-orbit Hamiltonian for self-gravitating binaries
• Graviton-mediated scattering amplitudes from the quantum effective action
• Generalised Proca Theories in Teleparallel Gravity
• Multicritical Landau-Potts field theory
• Light charged fermions in quantum gravity
• Higher derivatives in Type II and M-theory on Calabi-Yau threefolds
• Critical chiral Heisenberg model with the functional renormalization group
• Influence of internal structure on the motion of test bodies in extreme mass ratio situations
• A brief introduction to Cadabra: A tool for tensor computations in General Relativity
• The ghost of vector fields in compact stars
• Toward Second-Order Self-Force for Eccentric Extreme-Mass Ratio Inspirals in Schwarzschild Spacetime
• Local expansion mechanisms for quantum-scale wormholes. [europepmc]

Related

• Simplifying Tensor Polynomials with Indices
• Group-theoretic Approach for Symbolic Tensor Manipulation: I. Free Indices
• Nondimensional Simplification of Tensor Polynomials with Indices
• Hiding canonicalisation in tensor computer algebra
• The Continuous Tensor Abstraction: Where Indices are Real