Source-linked AI summary
xPerm: fast index canonicalization for tensor computer algebra
Jose M. Martin-Garcia
TL;DR
xPerm implements the Butler-Portugal algorithm for tensor index canonicalization under permutation symmetries through a Mathematica package and a C subroutine. Tests show effectively polynomial performance in typical cases, with one exponential case, and demonstrate handling of up to 100 indices in a few seconds.
Problem
Tensor computer algebra needs efficient index canonicalization because symmetry handling grows as n! with the number of indices.
Method
xPerm combines a Mathematica package for permutation-group manipulation with a C subroutine specialized in tensor index canonicalization, implementing the Butler-Portugal algorithm.
Results
xPerm is reported as the fastest index canonicalizer, with tests showing effectively polynomial performance and manipulation of 100 indices in a few seconds.
Takeaways & Limitations
xPerm supports large-scale tensor computer algebra and has enabled investigations in differential geometry and General Relativity.
Takeaways & Limitations
The Butler-Portugal algorithm has global exponential efficiency in the number of indices, although this exponential behavior appears only in a small subset of practical cases.
Abstract
from arXiv · showhide
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.
Program summary
xPerm is a C and Mathematica program for canonicalizing indexed expressions under permutation symmetries. It runs on common computer platforms and requires modest resources for typical data.
- Program summary: xPerm has been tested on Linux, Unix, Windows XP, and MacOS.
- Program summary: xPerm canonicalizes indexed expressions with respect to permutation symmetries using the Butler-Portugal algorithm.The implementation combines C and Mathematica components.
- Program summary: The program is written in C and Mathematica, with Mathematica version 5.0 or higher required.
- Program summary: Typical execution requires 20 Mbyte of memory and one processor.
1 Introduction
Tensor computer algebra addresses the combinatorial difficulty of calculations involving high dimensions and many indices. The paper introduces xPerm as a new Butler-Portugal implementation combining Mathematica and C components, with later sections evaluating its efficiency.
- 1 Introduction: Tensor calculations become difficult because coordinate expansions grow as n^d while symmetry handling grows as n!.
- 1 Introduction: Traditional permutation-listing methods require exponential time and memory, becoming slow for expressions with several dozen indices.
- 1 Introduction: The paper presents a new implementation of the Butler-Portugal algorithm for index canonicalization.
- 1 Introduction: The implementation combines a Mathematica package for large permutation groups with a C subroutine specialized in index canonicalization.
- 1 Introduction: The paper analyzes three nontrivial problems with examples and timings before presenting its conclusions.
2 The algorithms
The algorithms represent tensor-index canonicalization through permutations, signed symmetries, and double cosets. Butler-Portugal uses strong generating sets to find canonical representatives, with extensions for index types and component indices.
- 2 The algorithms: A tensor is represented by a head symbol and ordered slots, with paired symbols denoting contractions and integers representing component indices.
- 2 The algorithms: Canonicalization sorts index configurations by predefined priorities and represents the required rearrangement as a permutation.The paper reports that placing paired indices consecutively can improve efficiency.
- 2 The algorithms: Tensor permutation symmetries use signed permutations because rearrangements may preserve a tensor or change its sign.
- 2 The algorithms: Index canonicalization can be reduced to finding a canonical representative of the double coset S · g · D.
- 2 The algorithms: Strong generating sets efficiently represent permutation groups through bases and stabilizer subgroups.The Schreier-Sims algorithm can obtain these structures from a normal generating set.
- 2 The algorithms: Butler-Portugal sequentially determines the canonical permutation using the slot-symmetry group and an index-symmetry group of form D = DE · DM.
- 2 The algorithms: The algorithm is globally exponential because it uses an intersection algorithm, although its exponential behavior appears only in a small subset of practical cases.
- 2 The algorithms: The implementation extends the method to different index types and repeated component indices because their group actions are disjoint.The component-index groups require minor modifications to the algorithm.
3 A Mathematica implementation
The Mathematica implementation provides general permutation-group tools and index-canonicalization algorithms, including a two-step canonicalization workflow for free, dummy, and component indices.
- Permutation and group algorithms: xPerm offers permutation representations, translation, products, inverses, group construction, orbit and stabilizer tools, and Schreier-Sims strong-generating-set construction.Its scope includes efficient manipulation of large permutation groups, though it is more limited than MAGMA or GAP.
- Index canonicalization: The package implements RightCosetRepresentative, DoubleCosetRepresentative, and CanonicalPerm for index canonicalization.CanonicalPerm combines the algorithms after free indices are canonicalized first, followed by dummy and component indices.
- Index canonicalization: The canonicalization workflow handles slot symmetries of tensor products, including pair antisymmetries and exchanges within and between Riemann tensors.The example yields the canonical expression Rabbc Rd1c1.
- Index canonicalization: Dummy indices are specified with DummySet by vector space and metric symmetry, while repeated component indices use RepeatedSet.Other indices in the canonical list are treated as free.
- Implementation options: Canonicalization can run in pure Mathematica or through the faster compiled xPerm-C executable linked with MathLink.The MathLink -> False and MathLink -> True options select the two implementations.
4 The C code for the canonicalizer
The C implementation recodes the canonicalizer and permutation operations for speed, while retaining identical Mathematica output and supporting external linking.
- C implementation: All index-canonicalization algorithms were recoded in 2400 lines of C99 code to increase system speed.The code requires a modern C compiler, such as GNU gcc, on supported platforms.
- Permutation representation: xPerm-C represents permutations as image lists and stores the sign in an additional pair of points.For example, a positive permutation ends with 5,6, whereas its negative form ends with 6,5.
- Permutation operations: The C implementation provides efficient permutation products and inverses, along with operations for images, stable points, stabilizers, orbits, and Schreier vectors.Generating sets of m permutations of degree n are stored as m×n integers.
- Performance examples: Schreier-Sims is included for constructing strong generating sets, taking 5 seconds for a 48-index Rubik’s-group example and 2.5 seconds for a 276-point Conway group.The examples involve group orders of 4 · 10^19 and 5 · 10^11, respectively.
- Integration: The C code can be linked from other programs through a provided external interface and MathLink template.The Mathematica package can call the compiled executable through the MathLink protocol.
5 Examples and timings
The timing experiments show that xPerm’s Butler-Portugal implementation handles large index-canonicalization problems efficiently, while traditional methods can become exponential. Performance varies with problem structure, especially between zero and nonzero results and in specially hard cases.
- Example 1: All systems correctly identify expression (1) as zero for odd n, while xPerm-C handles 100 indices within a few seconds.The comparison includes MathTensor, TTC, Canon, pure Mathematica, and C-based implementations.
- Example 1: Traditional canonicalizers show exponential timing growth, whereas Butler-Portugal implementations exhibit effectively polynomial behavior.Figure 1 compares timings on a logarithmic axis across several tensor canonicalizers.
- Example 2: For random contracted Riemann monomials, zero results follow roughly n^3 timing growth, whereas nonzero results show dispersion with average growth near n^5.xPerm treats trivial and nontrivial zeros uniformly rather than using a special zero-detection rule.
- Example 2: xPerm-C canonicalizes products of up to 50 Riemann tensors, corresponding to 200 indices, while MathTensor cannot proceed beyond n = 9 with 1 Gbyte RAM.The xPerm timings are shown for both zero and nonzero results, with a reference curve t(n) = 15 n^3 µs.
- Example 3: Among one million degree-10 Riemann invariants, all zero cases finish in less than 0.1 s, while several nonzero cases take more than a second.The hardest cases are believed to include cyclic contractions of the form R^a1b1_a2b2 R^a2b2_a3b3 ... R^anbn_a1b1.
- Hard case: The cyclic antisymmetric-tensor case requires listing 2^n × 2^n permutations internally, making the Butler-Portugal computation exponential in n.Replacing antisymmetric index pairs with single indices converts the problem to one involving a symmetric tensor and restores near-Example-1 efficiency.
6 Conclusions
The paper presents xPerm as a free-software implementation of Butler-Portugal index canonicalization, combining Mathematica and C components. Timings on nontrivial examples identify it as the fastest index canonicalizer reported and connect it to large-scale differential-geometry computations.
- Conclusions: xPerm is a free-software package for manipulating large permutation groups in Mathematica, with index canonicalization under tensor permutation symmetries as its main objective.Its C code is available for linking by other free-software packages.
- Conclusions: The implementation uses the Butler-Portugal algorithm, whose behavior is effectively polynomial in the number of indices rather than exponential like traditional algorithms.The conclusion frames this contrast as the central computational advantage of xPerm.
- Conclusions: Timing comparisons on nontrivial computations support the author’s claim that xPerm is currently the fastest index canonicalizer.The claim is explicitly qualified as being based on the author’s knowledge and reported comparisons.
- Applications: xPerm has been used in projects involving Einstein-equation hyperbolicity, Bel-tensor evolution equations, and third post-Newtonian gravitational-wave polarization.These examples are presented as projects made possible only through use of xPerm.
- Software use: The C code is already the computational core of cadabra, and other free-software packages are encouraged to link to it for faster index canonicalization.Users of linked combinations are required to cite the publication.
A Prototypes of C functions
The C prototypes expose group-theoretic preprocessing, group-order and membership operations, and double-coset canonicalization for tensor index permutations. The canonicalization interface accepts permutation, symmetry-group, index-type, metric, dummy-index, and repeated-index data, then returns a canonical permutation.
- Group preprocessing: schreier_sims converts a generating set into a strong generating set relative to a base and reports the resulting base, generators, and generator count.Its inputs include the original base, generating set, group size, and permutation degree.
- Group operations: order_of_group takes a base and strong generating set and returns the order of the generated permutation group.The function uses the same core group-description inputs as the preceding prototype.
- Group operations: perm_member tests whether a supplied permutation belongs to a group and returns 1 for membership or 0 otherwise.The membership test operates on a strong generating set relative to a base.
- Double-coset canonicalization: canonical_perm_ext returns a canonical representative for a permutation using slot symmetries together with free, dummy, and repeated-index information.The interface also accepts metric symmetries and outputs cperm, the canonical permutation.
- Double-coset canonicalization: The canonicalization prototype can receive a permutation of degree n, a strong-generating-set flag, a base, generators, free indices, dummy pairs, metric symmetry, repeated-set lengths, and repeated indices.The example input uses n = 10 and encodes the permutation sign in its final two points.