On the complexity of multiplication in the Iwahori–Hecke algebra of the symmetric group

Alice C. Niemeyer; Götz Pfeiffer; Cheryl E. Praeger

doi:10.1016/j.jsc.2016.09.001

On the complexity of multiplication in the Iwahori–Hecke algebra of the symmetric group

Alice C. Niemeyer
, Götz Pfeiffer
, Cheryl E. Praeger

Mathematics

RWTH Aachen University
The University of Western Australia

Research output: Contribution to a Journal (Peer & Non Peer) › Article › peer-review

Abstract

We present new efficient data structures for elements of Coxeter groups of type A_m and their associated Iwahori–Hecke algebras H(A_m). Usually, elements of H(A_m) are represented as simple coefficient list of length M=(m+1)! with respect to the standard basis, indexed by the elements of the Coxeter group. In the new data structure, elements of H(A_m) are represented as nested coefficient lists. While the cost of addition is the same in both data structures, the new data structure leads to a huge improvement in the cost of multiplication in H(A_m).

Original language	English
Pages (from-to)	817-832
Number of pages	16
Journal	Journal of Symbolic Computation
Volume	80
DOIs	https://doi.org/10.1016/j.jsc.2016.09.001
Publication status	Published - 1 May 2017

Keywords

Complexity
Finite Coxeter group
Iwahori–Hecke algebra
Symmetric group

Access to Document

10.1016/j.jsc.2016.09.001

Cite this

@article{3eb8714b3cb8482992a26f11dce65004,

title = "On the complexity of multiplication in the Iwahori–Hecke algebra of the symmetric group",

abstract = "We present new efficient data structures for elements of Coxeter groups of type Am and their associated Iwahori–Hecke algebras H(Am). Usually, elements of H(Am) are represented as simple coefficient list of length M=(m+1)! with respect to the standard basis, indexed by the elements of the Coxeter group. In the new data structure, elements of H(Am) are represented as nested coefficient lists. While the cost of addition is the same in both data structures, the new data structure leads to a huge improvement in the cost of multiplication in H(Am).",

keywords = "Complexity, Finite Coxeter group, Iwahori–Hecke algebra, Symmetric group",

author = "Niemeyer, \{Alice C.\} and G{\"o}tz Pfeiffer and Praeger, \{Cheryl E.\}",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Ltd",

year = "2017",

month = may,

day = "1",

doi = "10.1016/j.jsc.2016.09.001",

language = "English",

volume = "80",

pages = "817--832",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press",

}

TY - JOUR

T1 - On the complexity of multiplication in the Iwahori–Hecke algebra of the symmetric group

AU - Niemeyer, Alice C.

AU - Pfeiffer, Götz

AU - Praeger, Cheryl E.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - We present new efficient data structures for elements of Coxeter groups of type Am and their associated Iwahori–Hecke algebras H(Am). Usually, elements of H(Am) are represented as simple coefficient list of length M=(m+1)! with respect to the standard basis, indexed by the elements of the Coxeter group. In the new data structure, elements of H(Am) are represented as nested coefficient lists. While the cost of addition is the same in both data structures, the new data structure leads to a huge improvement in the cost of multiplication in H(Am).

AB - We present new efficient data structures for elements of Coxeter groups of type Am and their associated Iwahori–Hecke algebras H(Am). Usually, elements of H(Am) are represented as simple coefficient list of length M=(m+1)! with respect to the standard basis, indexed by the elements of the Coxeter group. In the new data structure, elements of H(Am) are represented as nested coefficient lists. While the cost of addition is the same in both data structures, the new data structure leads to a huge improvement in the cost of multiplication in H(Am).

KW - Complexity

KW - Finite Coxeter group

KW - Iwahori–Hecke algebra

KW - Symmetric group

UR - https://www.scopus.com/pages/publications/84994802366

U2 - 10.1016/j.jsc.2016.09.001

DO - 10.1016/j.jsc.2016.09.001

M3 - Article

SN - 0747-7171

VL - 80

SP - 817

EP - 832

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

ER -

On the complexity of multiplication in the Iwahori–Hecke algebra of the symmetric group

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this