On the Complexity of Multiplication in the Iwahori--Hecke Algebra of the Symmetric Group

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)$.