×

xPerm: fast index canonicalization for tensor computer algebra. (English) Zbl 1197.15002

Summary: 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.

MSC:

15-04 Software, source code, etc. for problems pertaining to linear algebra
16-04 Software, source code, etc. for problems pertaining to associative rings and algebras
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] MacCallum, M. A.H., Int. J. Mod. Phys. A, 17, 2707-2710 (2002)
[2] Manssur, L. R.U.; Portugal, R.; Svaiter, B. F., Int. J. Mod. Phys. C, 13, 859-879 (2002)
[3] J.M. Martín-García, xAct, Efficient tensor computer algebra, http://metric.iem.csic.es/Martin-Garcia/xAct/, 2002-2008; J.M. Martín-García, xAct, Efficient tensor computer algebra, http://metric.iem.csic.es/Martin-Garcia/xAct/, 2002-2008
[4] Portugal, R., J. Phys. A: Math. Gen., 32, 7779-7789 (1999)
[5] Rodionov, A. Ya.; Taranov, A. Yu., (Proc. EUROCAL’87. Proc. EUROCAL’87, Lecture Notes in Comput. Sci., vol. 378 (1989), Springer), 192
[6] Butler, G., On computing double coset representatives in permutation groups, (Atkinson, M. D., Computational Group Theory (1984), Academic Press), 283
[7] Butler, G., Fundamental Algorithms for Permutation Groups (1991), Springer-Verlag: Springer-Verlag Berlin · Zbl 0785.20001
[8] Manssur, L. R.U.; Portugal, R., Canon, Comp. Phys. Commun., 157, 173-180 (2004) · Zbl 1196.68331
[9] MAGMA Computational Algebra System, http://magma.maths.usyd.edu.au/magma/; MAGMA Computational Algebra System, http://magma.maths.usyd.edu.au/magma/
[10] GAP—Groups, Algorithms, Programming, http://www-gap.mcs.st-and.ac.uk/; GAP—Groups, Algorithms, Programming, http://www-gap.mcs.st-and.ac.uk/
[11] Parker, L.; Christensen, S. M., MathTensor: A System for Doing Tensor Analysis by Computer (1994), Addison-Wesley: Addison-Wesley Reading, MA
[12] Balfagón, A.; Castellví, P.; Jaén, X., Tools of tensor calculus · Zbl 0967.83012
[13] Martín-García, J. M.; Portugal, R.; Manssur, L. R.U., Invar, Comp. Phys. Commun., 177, 640-648 (2007) · Zbl 1196.15006
[14] Martín-García, J. M.; Yllanes, D.; Portugal, R., Invar2, Comp. Phys. Commun. (2008)
[15] Gundlach, C.; Martín-García, J. M., Phys. Rev. D, 74, 024016 (2006)
[16] García-Parrado, A., Class. Quantum Grav., 24, 015006 (2008)
[17] Blanchet, L.; Faye, G.; Iyer, B. R.; Sinha, S.
[18] Peeters, K., Cadabra, Comp. Phys. Commun., 176, 550-558 (2007) · Zbl 1196.68333
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.