xPerm: fast index canonicalization for tensor computer algebra

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

Program title: xPermCatalogue identifier: AEBH_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEBH_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 93 582No. of bytes in distributed program, including test data, etc.: 1 537 832Distribution format: tar.gzProgramming language: C and Mathematica (version 5.0 or higher)Computer: Any computer running C and Mathematica (version 5.0 or higher)Operating system: Linux, Unix, Windows XP, MacOSRAM:: 20 MbyteWord size: 64 or 32 bitsClassification: 1.5, 5Nature of problem: Canonicalization of indexed expressions with respect to permutation symmetries.Solution method: The Butler-Portugal algorithm.Restrictions: Multiterm symmetries are not considered.Running time: A few seconds with generic expressions of up to 100 indices. The xPermDoc.nb notebook supplied with the distribution takes approximately one and a half hours to execute in full.