Faster Tensor Canonicalization

Faster Tensor Canonicalization. Benjamin E. Niehoff February, 2017.

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.

@article{benjamin_e._niehoff_faster_2017,
	title = {Faster {Tensor} {Canonicalization}},
	url = {https://arxiv.org/abs/1702.08114#},
	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.},
	author = {{Benjamin E. Niehoff}},
	month = feb,
	year = {2017},
	keywords = {Multilinear algebra, Tensors, mentions sympy},
}

Downloads: 0

{"_id":"rBsoZBzRheH6Zk6MF","bibbaseid":"benjamineniehoff-fastertensorcanonicalization-2017","authorIDs":[],"author_short":["Benjamin E. Niehoff"],"bibdata":{"bibtype":"article","type":"article","title":"Faster Tensor Canonicalization","url":"https://arxiv.org/abs/1702.08114#","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.","author":[{"firstnames":[],"propositions":[],"lastnames":["Benjamin E. Niehoff"],"suffixes":[]}],"month":"February","year":"2017","keywords":"Multilinear algebra, Tensors, mentions sympy","bibtex":"@article{benjamin_e._niehoff_faster_2017,\n\ttitle = {Faster {Tensor} {Canonicalization}},\n\turl = {https://arxiv.org/abs/1702.08114#},\n\tabstract = {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.},\n\tauthor = {{Benjamin E. Niehoff}},\n\tmonth = feb,\n\tyear = {2017},\n\tkeywords = {Multilinear algebra, Tensors, mentions sympy},\n}\n\n","author_short":["Benjamin E. Niehoff"],"key":"benjamin_e._niehoff_faster_2017","id":"benjamin_e._niehoff_faster_2017","bibbaseid":"benjamineniehoff-fastertensorcanonicalization-2017","role":"author","urls":{"Paper":"https://arxiv.org/abs/1702.08114#"},"keyword":["Multilinear algebra","Tensors","mentions sympy"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"article","biburl":"https://bibbase.org/zotero-group/nicoguaro/525293","creationDate":"2020-07-15T19:11:20.645Z","downloads":0,"keywords":["multilinear algebra","tensors","mentions sympy"],"search_terms":["faster","tensor","canonicalization","benjamin e. niehoff"],"title":"Faster Tensor Canonicalization","year":2017,"dataSources":["YtBDXPDiQEyhyEDZC","fhHfrQgj3AaGp7e9E","qzbMjEJf5d9Lk78vE","45tA9RFoXA9XeH4MM","MeSgs2KDKZo3bEbxH","nSXCrcahhCNfzvXEY","ecatNAsyr4f2iQyGq","tpWeaaCgFjPTYCjg3"]}