On the complexity of multiplication in the Iwahori–Hecke algebra of the symmetric group. (May 2017) - Niemeyer, Alice C.; Pfeiffer, Götz; Praeger, Cheryl E.
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 ) .